Iskanje po katalogu digitalne knjižnice

Opis: V tej nalogi bomo obravnavali pojma povezanost po povezavah in povezanost po vozliščih v produktih grafov. Drugi cilj bo opisati strukturo in ostale lastnosti najmanjših presečnih množic vozlišč in najmanjših presečnih množic povezav v produktih grafov. Osredotočili se bomo predvsem na kartezični, direktni, krepki in leksikografski produkt grafov. Zanimalo nas bo, kako izraziti povezanost produkta z lastnostmi posameznih faktorjev produkta, kot so najmanjša stopnja, red grafa in povezanost. Pri direktnem produktu grafov bomo ugotovili, da je povezanost po povezavah odvisna od povezanosti faktorjev, pa tudi od tega, kako daleč sta faktorja $G$ in $H$ od tega, da bi bila dvodelna. Nato bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav kartezičnih produktov grafov. Podan bo dokaz trditve $lambda(G , Box , H)= textrm{min}left{lambda(G)left|V(H)right|,lambda(H)left|V(G)right|,delta(G)+delta(H)right}.$ Dokaz podobne trditve za povezanost po vozliščih kartezičnega produkta bo naveden v nadaljevanju. Na koncu bomo obravnavali velikost in strukturo najmanjših presečnih množic povezav krepkih produktov grafov in povezanost v leksikografskem produktu.
Ključne besede: produkti grafov, kartezični produkt, direktni produkt, krepki produkt, leksikografski produkt, povezanost.
Objavljeno v DKUM: 23.08.2016; Ogledov: 1681; Prenosov: 198
Celotno besedilo (3,58 MB)

Opis: Pravilno barvanje vozlišč grafa kjer vsak barvni razred vsebuje vozlišče, ki ima soseda v vseh preostalih barvnih razredih, imenujemo b-barvanje. Največje naravno število ▫$varphi (G)$▫, za katero obstaja b-barvanje grafa ▫$G$▫, imenujemo b-kromatično število. Določimo nekatere spodnje in zgornje meje b-kromatičnega števila za krepki produkt ▫$G,boxtimes, H$▫, leksikografski produkt ▫$G[H]$▫ in za direktni produkt ▫$G,times, H$▫. Prav tako določimo nekatere točne vrednosti za produkte poti, ciklov, zvezd in polnih dvodelnih grafov. Pokažemo tudi, da lahko določimo b-kromatično število za ▫$P_n ,boxtimes, H$▫, ▫$C_n ,boxtimes, H$▫, ▫$P_n[H]$▫, ▫$C_n[H]$▫ in ▫$K_{m,n}[H]$▫ za poljuben graf ▫$H$▫, če sta le ▫$m$▫ in ▫$n$▫ dovolj veliki.
Ključne besede: teorija grafov, b-kromatično število, krepki produkt, leksikografski produkt, direktni produkt, graph theory, b-chromatic number, strong product, lexicographic product, direct product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1190; Prenosov: 89
Povezava na celotno besedilo

Opis: An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.
Ključne besede: matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1305; Prenosov: 41
Povezava na celotno besedilo

Opis: Naj bo ▫$G = times_{i=1}^nC_{ell_i}$▫ direktni produkt ciklov. Dokazano je, da za vsak ▫$r ge 1$▫ in za vsak ▫$n ge 2$▫ velja naslednje. Če je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫, tedaj vsaka povezana komponenta grafa ▫$G$▫ vsebuje ▫$r$▫-popolno kodo. Po drugi strani je tudi dokazano, da če koda grafa ▫$G$▫ vsebuje izbrano točko in njene lokalno kanonične točke, tedaj je vsak ▫$ell_i$▫ večkratnik od ▫$r^n + (r+1)^n$▫. Nadalje je dokazano, da je ▫$r$▫-popolna koda ▫$(r ge 2)$▫ grafa ▫$G$▫ enolično določena z ▫$n$▫ točkami. Postavljena je domneva, da za ▫$r ge 2$▫ ne obstajajo nobene druge kode v $G$ razen tistih, ki so konstruirane v članku.
Ključne besede: matematika, teorija grafov, korekcijske kode, direktni produkt grafov, popolne kode, cikli, mathematics, graph theory, error-correcting codes, direct product of graphs, perfect codes, cycles
Objavljeno v DKUM: 10.07.2015; Ogledov: 24186; Prenosov: 101
Povezava na celotno besedilo

Opis: 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.
Ključne besede: 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
Objavljeno v DKUM: 04.04.2013; Ogledov: 3284; Prenosov: 185
Celotno besedilo (466,86 KB)