Iskanje po katalogu digitalne knjižnice

Opis: Doktorska disertacija obravnava koncepta množice vozlišč v splošni legi v grafih in l-razdaljno-uravnoteženost grafov. Oba koncepta sta bila v tej obliki vpeljana nedavno, splošna lega leta 2018 v članku avtorjev Manuela in Klavžarja, l-razdaljna uravnoteženost pa v doktorski diseratciji Freliha leta 2014. V disertaciji so predstavljeni novi rezultati, ki so večinoma povezani z različnimi grafovskimi produkti. Dokazana je točna vrednost gp-števila v kartezičnem produktu poljubnega števila poti, natančneje, da velja $\gp(P^{\cp,n}) = 2^{2^{n-1}}$. Dokazana je točna vrednost gp-števila v produktu poti in cikla in produkta dveh ciklov. Dokazana je tudi točna vrednost gp-števila v nekaterih Kneserjevih grafih. V razdelku, ki se ukvarja z l-razdaljno-uravnoteženostjo, je pokazan pogoj, kdaj je leksikografski produkt grafov $G[H]$ $\ell$-razdaljno-uravnotežen za poljuben $\ell \in \{3,\ldots,\diam(G)\}$. Prav tako je dokazano, kdaj je $\ell$-razdaljno-uravnotežen korona produkt. Določimo pa tudi pogoj, kdaj je $\ell$-razdaljno uravnotežen kartezični produkt $G\cp K_n.$
Ključne besede: teorija grafov, množica vozlišč v splošni legi, gp-število, grafovski produkti, poti, cikli, razdaljno-uravnoteženi grafi, l-razdaljno-uravnoteženi grafi
Objavljeno v DKUM: 07.10.2022; Ogledov: 785; Prenosov: 67
Celotno besedilo (965,92 KB)

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: 203
Celotno besedilo (3,58 MB)

Opis: Grafi zastraženih inverzov tvorijo obsežno nedvodelno posplošitev medianskih grafov. Z uporabo določenega naravnega barvanja povezav, ki je porojeno z relacijo vzporednosti med predvlakni grafov zastraženih inverzov, vpeljemo križni graf grafa zastraženega inverza ▫$G$▫ kot graf, katerega vozlišča so barve, dve barvi pa sta sosednji, če se križata na kakem induciranem 4-ciklu v grafu ▫$G$▫. V članku pokažemo, da je graf zastraženega inverza 2-povezan natanko tedaj, ko je njegov križni graf povezan. Karakteriziramo tiste grafe zastraženih inverzov, ki imajo poln križni graf pa tudi tiste s tetivnim križnim grafom.
Ključne besede: matematika, teorija grafov, medianski grafi, zastražene množice, predvlakna, kartezični produkt grafov, ekspanzija, mathematics, graph theory, median graphs, gated sets, prefibers, kartezični produkti, expansion
Objavljeno v DKUM: 10.07.2015; Ogledov: 1422; Prenosov: 94
Povezava na celotno besedilo

Opis: The distinguishing number ▫$D(G)$▫ of a graph ▫$G$▫ is the least integer ▫$d$▫ such that there is a ▫$d$▫-labeling of the vertices of ▫$G$▫ which is not preserved by any nontrivial automorphism. For a graph ▫$G$▫ let ▫$G^r$▫ be the ▫$r$▫-th power of ▫$G$▫ with respect to the Cartesian product. It is proved that ▫$D(G^r) = 2$▫ for any connected graph ▫$G$▫ with at least 3 vertices and for any ▫$r = 3$▫. This confirms and strengthens a conjecture of Albertson. Other graph products are also considered and a refinement of the Russell and Sundaram motion lemma is proved.
Ključne besede: matematika, teorija grafov, razlikovalno število, grafovski avtomorfizem, produkti grafov, mathematics, graph theory, distingushing number, graph automorphism, products of graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1260; Prenosov: 89
Povezava na celotno besedilo

Opis: V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov.
Ključne besede: matematika, teorija grafov, razdalja, razdaljno uravnoteženi grafi, produkti grafov, povezanost, mathematics, graph theory, graph distance, distance-balanced graphs, graph products, connectivity
Objavljeno v DKUM: 10.07.2015; Ogledov: 1739; Prenosov: 95
Povezava na celotno besedilo