| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 10 / 13
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
CELOŠTEVILSKE DOMINACIJSKE INVARIANTE NA GRAFIH
Luka Komovec, 2009, diplomsko delo

Opis: Naj bo Y podmnožica množice celih števil in G = (V,,E) graf. Funkcija, ki vsakemu vozlišču priredi neko vrednost iz množice Y, tako da je seštevek vrednosti v soseščini vsakega vozlišča vsaj 1, se imenuje celoštevilska dominacijska funkcija grafa G. Vrednost celoštevilske dominacijske funkcije v poljubni podmnožici S množice V definiramo kot seštevek vrednosti v vsakem vozlišču iz S. Teža celoštevilske dominacijske funkcije je vrednost funkcije v množici vozlišč V. Poiskati želimo po teži najmanjšo celoštevilsko dominacijsko funkcijo grafa G. V tem delu so predstavljene variacije različnih celoštevilskih dominacij, kot so {k}-dominacija, k-kratna dominacija, predznačena dominacija in minus dominacija, ki jih obravnavamo na razredih grafov kot so poti, cikli, pahljače, kolesa, ponve in trampolini. Podan je algoritem, ki v linearnem času reši problem L-dominacije na strogo tetivnih grafih. Prav tako je podana časovna zahtevnost izračuna naštetih celoštevilskih dominacijskih invariant za razrede dualno tetivnih, dvojno tetivnih in ravninskih grafov. Na koncu je na podoben način predstavljena 2-mavrična dominacija.
Ključne besede: celoštevilska dominacija, k-kratna dominacija, predznačena dominacija, minus dominacija, {k}-dominacija, 2-mavrična dominacija, tetivni grafi, dualno tetivni grafi, dvojno tetivni grafi, strogo tetivni grafi
Objavljeno: 17.06.2009; Ogledov: 1831; Prenosov: 131
.pdf Celotno besedilo (501,60 KB)

2.
Algebra poti in dominantni problemi na grafovskih produktih
Polona Pavlič, 2013, doktorska disertacija

Opis: Različni problemi grafovskih invariant predstavljajo velik del študij na področju teorije grafov. Ker so ti problemi v veliki meri NP-polni, je smiselno iskati rešitve na določenih zanimivih družinah grafov. V tem delu se omejimo na probleme dominacije na družini poligrafov. To so grafi, ki izhajajo iz kemijske teorije grafov in so matematični model kemijske strukture polimera. V kemiji je polimer makromolekula, ki ima posebno ponavljajočo se strukturo molekul, povezanih s kovalentnimi vezmi. Mi se posebej omejimo na primere, ko so te ponavljajoče enote enake, oziroma v jeziku teorije grafov, ko so monografi izomorfni, ter so povezave med njimi enake. Taki grafi se imenujejo rotagrafi, če pa med prvim in zadnjim monografom ni povezav, imenujemo tak poligraf fasciagraf. S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov za fiksno velikost monografa lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant. Nazadnje še rešimo problem rimskega dominantnega števila na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominatnih parov za poljubna grafa podamo formulo, ki določi rimsko dominantno število njunega leksikografskega produkta. Podamo tudi nove neskončne družine rimskih grafov.
Ključne besede: grafovski produkt, dominacija, algebra poti, konstantni algoritem, mreža, torus
Objavljeno: 04.04.2013; Ogledov: 1484; Prenosov: 123
.pdf Celotno besedilo (1,51 MB)

3.
On the Roman domination in the lexicographic product of graphs
Tadeja Kraner Šumenjak, Polona Repolusk, Aleksandra Tepeh, 2012, izvirni znanstveni članek

Opis: A Roman dominating function of a graph ▫$G = (V,E)$▫ is a function ▫$f colon V to {0,1,2}$▫ such that every vertex with ▫$f(v) = 0$▫ is adjacent to some vertex with ▫$f(v) = 2$▫. The Roman domination number of ▫$G$▫ is the minimum of ▫$w(f) = sum_{v in V}f(v)$▫ over all such functions. Using a new concept of the so-called dominating couple we establish the Roman domination number of the lexicographic product of graphs. We also characterize Roman graphs among the lexicographic product of graphs.
Ključne besede: teorija grafov, rimska dominacija, popolna dominacija, leksikografski produkt, graph theory, Roman domination, total domination, lexicographic product
Objavljeno: 10.07.2015; Ogledov: 567; Prenosov: 57
URL Povezava na celotno besedilo

4.
Rainbow domination in the lexicographic product of graphs
Tadeja Kraner Šumenjak, Douglas F. Rall, Aleksandra Tepeh, 2013, izvirni znanstveni članek

Opis: Preslikava iz množice vozlišč grafa ▫$G$▫ v potenčno množico množice ▫${1,2,dots, k}$▫ se imenuje ▫$k$▫-mavrična dominantna funkcija, če za poljubno vozlišče ▫$v$▫ z lastnostjo ▫$f(v) = emptyset$▫ velja ▫${1,dots,k} = bigcup_{u in N(v)}f(u)$▫. Obravnavamo ▫$k$▫-mavrično dominantno število grafa ▫$G$▫, ▫$gamma_{rk}(G)$▫, ki je minimalna vsota (po vseh vozliščih grafa ▫$G$▫) moči podmnožic, ki so vozliščem dodeljena s ▫$k$▫-mavrično dominantno funkcijo. V članku se osredotočimo na 2-mavrično dominantno število leksikografskega produkta grafov in dokažemo natančno spodnjo in zgornjo mejo za to število. Dejansko pokažemo natančno vrednost za ▫$gamma_{r2}(G circ H)$▫, razen v primeru, ko je ▫$gamma_{r2}(H) = 3$▫ in obstaja taka minimalna 2-mavrična dominantna funkcija grafa $H$, ki nekemu vozlišču v grafu ▫$H$▫ dodeli oznako ▫${1,2}$▫.
Ključne besede: dominacija, popolna dominacija, mavrična dominacija, leksikografski produkt, domination, total domination, rainbow domination, lexicographic product
Objavljeno: 10.07.2015; Ogledov: 462; Prenosov: 51
URL Povezava na celotno besedilo

5.
On integer domination in graphs and Vizing-like problems
Boštjan Brešar, Michael A. Henning, Sandi Klavžar, 2006, izvirni znanstveni članek

Opis: Nadaljujemo študij ▫${k}$▫-dominantnih funkcij v grafih (ali, kot bomo tudi rekli, celoštevilske dominacije), ki so jo začeli Domke, Hedetniemi, Laskar in Fricke. Za celo število ▫$k ge 1$▫ je funkcija ▫$f: V(G) to {0,1,...,k}$▫, definirana na točkah grafa ▫$G$▫, ▫${k}$▫-dominantna funkcija, če je vsota funkcijskih vrednosti na vsaki zaprti okolici vsaj ▫$k$▫. Teža ▫${k}$▫-dominantne funkcije je vsota funkcijskih vrednosti po vseh točkah. ▫${k}$▫-dominantno število grafa ▫$G$▫ je najmanjša teža ▫${k}$▫-dominantne funkcije na ▫$G$▫. Obravnavamo ▫${k}$▫-dominantno število kartezičnega produkta grafov, predvsem probleme povezane s slavno Vizingovo domnevo. Študirana je tudi povezava med ▫${k}$▫-dominantnim številom in drugimi tipi dominacijskih parametrov.
Ključne besede: matematika, teorija grafov, ▫${k}$▫-dominantna funkcija, celoštevilska dominacija, Vizingova domneva, kartezični produkt grafov, mathematics, graph theory, ▫${k}$▫-dominating function, integer domination, Vizing's conjecture, Cartesian product
Objavljeno: 10.07.2015; Ogledov: 427; Prenosov: 31
URL Povezava na celotno besedilo

6.
Dominating direct products of graphs
Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek

Opis: Dokazana je zgornja meja za dominantno število direktnega produkta grafov. V posebnem primeru iz meje sledi, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma (G times H) le 3gamma(G)gamma(H)$▫. Konstruirani so grafi s poljubno velikimi dominantnimi števili, za katere je ta meja dosežena. Za gornje dominantno število dokažemo, da velja ▫$Gamma(G times H) ge Gamma(G)Gamma(H)$▫, s čimer je potrjena domneva iz [R. Nowakowski, D.F. Rall, Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 (1996) 53-79]. Nazadnje za dominacijo v parih direktnih produktov dokažemo, da za poljubna grafa ▫$G$▫ in ▫$H$▫ velja ▫$gamma_{rm{pr}}(G times H) le gamma_{rm{pr}} (G)gamma_{rm{pr}}(H)$▫. Predstavimo tudi neskončne družine grafov, pri katerih je ta meja dosežena.
Ključne besede: matematika, teorija grafov, dominacija, dominacija v parih, gornja dominacija, kartezični produkt grafov, mathematics, graph theory, domination, paired-domination, upper domination, direct product
Objavljeno: 10.07.2015; Ogledov: 332; Prenosov: 50
URL Povezava na celotno besedilo

7.
Fair reception and Vizing's conjecture
Boštjan Brešar, Douglas F. Rall, 2009, izvirni znanstveni članek

Opis: Vpeljemo koncept poštenega sprejema grafa, ki je povezan z njegovim dominantnim številom. Dokažemo, da za vse grafe, ki imajo pošten sprejem velikosti njihovega dominantnega števila, velja Vizingova domneva o dominantnem številu kartezičnega produkta grafov, s čimer posplošimo dobro znan rezultat Barcalkina in Germana o razstavljivih grafih. S kombiniranjem nav sega koncepta in rezultata Aharonija, Bergerja in Ziva dobimo alternativen dokaz izreka Aharonija in Szaba, ki pravi, da tetivni grafi zadoščajo Vizingovi domnevi. Predstavimo tudi novo neskončno družino grafov, ki zadoščajo Vizingovi domnevi.
Ključne besede: matematika, teorija grafov, dominacija, kartezični produkt grafov, Vizingova domneva, mathematics, graph theory, domination, Cartesian product of graphs, Vizing's conjecture
Objavljeno: 10.07.2015; Ogledov: 470; Prenosov: 49
URL Povezava na celotno besedilo

8.
Vizing's conjecture: a survey and recent results
Boštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, Douglas F. Rall, 2009

Opis: Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.
Ključne besede: matematika, teorija grafov, kartezični produkt, dominacija, Vizingova domneva, mathematics, graph theory, Caretesian product, domination, Vizing's conjecture
Objavljeno: 10.07.2015; Ogledov: 322; Prenosov: 49
URL Povezava na celotno besedilo

9.
Vizing's conjecture: a survey and recent results
Boštjan Brešar, Paul Dorbec, Wayne Goddard, Bert L. Hartnell, Michael A. Henning, Sandi Klavžar, Douglas F. Rall, 2012, pregledni znanstveni članek

Opis: Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega ▫$K_{1,3}$▫ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve.
Ključne besede: matematika, teorija grafov, kartezični produkt, dominacija, Vizingova domneva, mathematics, graph theory, Caretesian product, domination, Vizing's conjecture
Objavljeno: 10.07.2015; Ogledov: 481; Prenosov: 38
URL Povezava na celotno besedilo

10.
A note on the domination number of the Cartesian products of paths and cycles
Polona Repolusk, Janez Žerovnik, 2011

Opis: Z uporabo algebraičnega pristopa implementiramo konstantni algoritem za računanje dominantnega števila kartezičnih produktov poti in ciklov. Podamo formule za dominantna števila ▫$gamma(P_n Box C_k)$▫ (za ▫$k leq 11$▫, ▫$n in {mathbb N}$)▫ in dominantna števila ▫$gamma(C_n Box P_k)$▫ in ▫$gamma(C_n Box C_k)$▫ (za ▫$k leq 6$▫, ▫$n in {mathbb N}$▫).
Ključne besede: teorija grafov, kartezični produkt, grid, torus, dominacija, algebra poti, konstantni algoritem, graph theory, Cartesian product, grid graph, torus, graph domination, path algebra, constant time algorithm
Objavljeno: 10.07.2015; Ogledov: 532; Prenosov: 17
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.34 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici