11. On domination numbers of graph bundlesBlaž Zmazek, Janez Žerovnik, 2005 Abstract: Let ▫$gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k ge 0$▫ there exists a Cartesian graph bundle ▫$B Box_varphi F$▫ such that ▫$gamma(B Box_varphi F) = gamma(B)gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$gamma(B boxtimes_varphi F) le gamma(B)gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$gamma(B boxtimes_varphi F) < gamma(B)gamma(F)$▫ are given.
Keywords: matematika, teorija grafov, kartezični produkt grafov, dominantno število, dominantna množica, grafovski sveženj, mathematics, graph theory, graph bundle, dominating set, domination number, Cartesian product
Published in DKUM: 10.07.2015; Views: 1616; Downloads: 98
 Link to full text |
12. Rimsko dominantno številoJasmina Starčevič, 2014, undergraduate thesis Abstract: V diplomskem delu je predstavljena t.i. rimska dominacija, gre za eno izmed različic običajne dominacije. V prvem delu so na kratko povzeti osnovni pojmi iz teorije grafov. V nadaljevanju govorimo o značilnostih dominantne množice in dominantnega števila.V tretjem delu podrobneje spoznamo lastnosti RDF in rimskega dominantnega števila.Proučevana so tudi rimska dominantna števila ciklov,poti, polnih n-delnih grafov,dreves in kartezičnega produkta.V zadnjem delu definiramo povezavo med vrednostjo dominantnega in rimskega dominantnega števila pri istih grafih.
Keywords: dominantno število, 2-pakiranje, rimska dominantna funkcija, rimsko dominantno število, rimski grafi
Published in DKUM: 03.04.2014; Views: 2176; Downloads: 133
 Full text (12,91 MB) |
13. Povezano dominantno število grafaRenato Smej, 2013, undergraduate thesis Abstract: V diplomskem delu je obravnavano povezano dominantno število grafa. Na začetku so podrobneje razloženi osnovni pojmi teorije grafov, ki so potrebni za razumevanje celotnega dela. V osrednjem delu so opisane lastnosti povezanega dominantnega števila grafa ter predstavljene družine grafov, za katere je dominantno število in povezano dominantno število grafa enako. Na koncu so opisani še povezano dominantno kritični grafi
in naštetih nekaj njihovih lastnosti.
Keywords: dominantno število, povezano dominantno število.
Published in DKUM: 08.01.2014; Views: 1621; Downloads: 150
Full text (420,34 KB) |
14. Direktni produkti polnih grafovGašper Mekiš, 2013, doctoral dissertation Abstract: Prvi del disertacije je posvečen neodvisnim dominantnim množicam direktnega produkta štirih polnih grafov. Eksplicitno so opisane T1-množice, tj. množice, kjer se poljubni par vozlišč ujema na natanko enem mestu. Glavni rezultat tega dela reče, da direktni produkt štirih polnih grafov premore idomatsko particijo na T1-množice natanko tedaj, ko sta reda vsaj dveh faktorjev deljiva s 3.
V nadaljevanju postane osrednja tema dominantno in polno dominantno število direktnega produkta končno mnogo polnih grafov. Za slednje grafe je podana spodnja meja, ki je točna, če so faktorji dovolj veliki v primerjavi s številom faktorjev. Najsplošnejši rezultat tega dela je spodnja meja za dominantno (in polno dominantno) število direktnega produkta poljubnih dveh grafov, ki je izražena z dominatnima številoma faktorjev. Opisane so neskončne družine grafov, ki zavzamejo enakost.
Zadnji del je posvečen mavrični povezanosti direktnega produkta. Podana je zgornja meja za mavrično povezanost direktnega produkta dveh grafov v odvisnosti od mavrične povezanosti faktorjev in še dveh podobnih invariant dobljenih s pomočjo lihih ciklov. Izkaže se, da so ravno polni grafi izjema omenjene meje. Za produkt dveh polnih grafov je dana točna vrednost (krepke) mavrične povezanosti. Kot dodatek so na koncu podani tudi nekateri rezultati glede ostalih treh standardnih grafovskih produktov.
Keywords: direktni produkt grafov, dominantna množica, dominantno število, idomatska particija, krepka mavrična povezanost, neodvisna množica, mavrična povezanost, polna dominantna množica, polni graf, polno dominantno število
Published in DKUM: 04.04.2013; Views: 3284; Downloads: 185
Full text (466,86 KB) |
15. NEENAKOSTI VIZINGOVEGA TIPA ZA RAZLIČNE DOMINACIJSKE INVARIANTEVika Koban, 2012, undergraduate thesis Abstract: Dominacija na grafih je intenzivno raziskovana veja v teoriji grafov. Leta 1963 je Vizing postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov kvečjemu večje od produkta njunih dominantih števil. Mnogo delnih rezultatov je bilo dokazanih, vendar pa je le-ta še vedno eden izmed največjih odprtih problemov v študiju dominacije na grafih. V tem diplomskem delu so v ospredju obravnavani najbolj znani izreki Vizingovega tipa za različne dominacijske invariante.
Na začetku predstavimo nekaj dejstev o dominaciji na kartezičnem produktu. Opišemo znan Clark-Suenov rezultat Vizingovega tipa in t.i. razstavljive grafe, za katere Vizingova domneva drži.
Drugi del se nanaša na pet dominacijskih invariant; totalno, celoštevilsko, zgornjo, deljeno dominantno število in dominacijo po parih. Predstavljeni so izreki Vizingovega tipa za posamezne dominacijske parametre, kot na primer izrek za deljeno-dominantno število, Ho-jev izrek o totalnem dominantnem številu in izrek Vizingovega tipa za zgornje dominantno število.
Keywords: dominantna množica, dominantno število, Vizingova domneva, dominacijske invariante
Published in DKUM: 11.09.2012; Views: 2126; Downloads: 255
Full text (715,88 KB) |
