1. Super dominantno število grafaTajda Remic, 2024, magistrsko delo Opis: Množica $D$ vozlišč grafa $G$ je super dominantna množica, če za vsako vozlišče $v \in V(G)-D$ obstaja vozlišče $u \in D$, ki je sosednje z $v$ in velja, da je $v$ edini sosed od $u$ v $V(G)-D$. Velikost najmanjše super dominantne množice grafa $G$ je super dominantno število grafa $G$, ki ga označujemo z $\gamma_{sp}(G)$.
V magistrskem delu raziskujemo lastnosti super dominantnega števila. V ta namen najprej predstavimo osnovne pojme na grafih, predstavimo nekaj pomembnih družin grafov in veliko različnih grafovskih invariant, ki so povezane s super dominantnim številom.
V drugem delu pričnemo z raziskovanjem super dominantnih množic. Najprej izračunamo super dominantno število za nekaj pomembnih družin grafov in dokažemo, da za vsak povezan graf na vsaj dveh vozliščih velja: $\frac{n}{2} \leq \gamma_{sp}(G)\leq |V(G)|-1$. Nato super dominantno število raziskujemo na drevesih. Dokažemo boljšo zgornjo mejo super dominantnega števila dreves in se ukvarjamo z grafi, ki to mejo dosežejo. Na koncu super dominantno število dreves navzgor omejimo še z $2$-dominantnim številom grafa. V zadnjem delu magistrske naloge predstavimo zvezo super dominantnega števila z mnogimi grafovskimi invariantami, kot so velikost največjega prirejanja, neodvisnostno število in mnoge druge.
Ključne besede: super dominantno število, super dominantna množica, drevo, neodvisnostno število, dominantno število, prirejanje
Objavljeno v DKUM: 11.06.2024; Ogledov: 153; Prenosov: 33
 Celotno besedilo (6,92 MB) |
2. Meje za mavrična dominantna števila : magistrsko deloKlavdija Zelko, 2023, magistrsko delo Opis: Mavrično dominacijo na grafu $G$, z (neprazno) množico vozlišč in povezav ter množico s $k$ barvami, opišemo kot funkcijo $f$, ki vsako vozlišče označi s poljubno podmnožico barv tako, da imajo vsa tista vozlišča, ki jim je prirejena prazna množica, v svoji soseščini vseh $k$ barv. Funkciji $f$ tedaj pravimo $k$-mavrična dominantna funkcija grafa $G$. Vsota moči vseh oznak na vozliščih je vrednost $k$-mavrično dominantne funkcije. Najmanjša vrednost izmed vseh takih funkcij na grafu $G$ se imenuje $k$-mavrično dominantno število grafa $G$. V magistrskem delu podamo nekaj točnih vrednosti in zgornjih mej za $k$-mavrična dominantna števila. Večji poudarek damo na meje za 2- in 3-mavrično dominantna števila. Dokažemo dve splošni zgornji meji 2-mavrično dominantnega števila ter opišemo meje za 3-mavrično dominantna števila. Na koncu dela sledijo meje za $k$-mavrično dominantna števila, za katera je $k > 3$. V nekaterih primerih opišemo družine grafov, ki dosežejo enakost meje in jih dokažemo.
Ključne besede: graf, dominantno število, mavrična dominantna funkcija, mavrično dominantno število
Objavljeno v DKUM: 02.02.2023; Ogledov: 766; Prenosov: 53
Celotno besedilo (3,91 MB) |
3. Grafi, ki dosežejo enakost v vizingovi domnevi : magistrsko deloAnamarija Lakner, 2022, magistrsko delo Opis: Vizing je leta 1968 postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov večje ali enako produktu njunih dominantnih števil. V magistrskem delu obravnavamo družine grafov, ki v tej domnevi dosežejo enakost.
V prvem delu magistrske naloge smo navedli pojme in trditve, ki jih potrebujemo za razumevanje glavnega problema naloge.
Drugo poglavje se nanaša na različne meje dominantnega števila kartezičnega produkta dveh grafov in družine grafov, ki zadoščajo Vizingovi domnevi.
V tretjem poglavju obravnavamo družine grafov, ki pod določenimi pogoji dosežejo enakost v Vizingovi domnevi, ter znane rezultate podamo v tabeli.
Ključne besede: dominantno število, dominantna množica, Vizingova domneva, enakost v Vizingovi domnevi
Objavljeno v DKUM: 28.10.2022; Ogledov: 573; Prenosov: 49
Celotno besedilo (568,89 KB) |
4. Anihilacijsko število grafa in njegova povezava s celotnim dominantnim številomLara Lužnic, 2019, magistrsko delo Opis: Anihilacijsko število grafa je največje naravno število k, za katerega velja, da vsota prvih k členov v nepadajočem zaporedju stopenj grafa ne presega števila povezav tega grafa. V magistrskem delu je predstavljena definicija anihilacijskega števila, nekatere njegove lastnosti ter njegova povezava s celotnim dominantnim številom grafa.
V prvem poglavju so predstavljeni osnovni pojmi in rezultati iz teorije grafov, ki jih potrebujemo za definiranje pojmov in dokazovanje v nadaljevanju. V drugem poglavju je na podlagi anihilacijskega procesa izpeljana definicija anihilacijska števila, opisana je povezava med anihilacijskim procesom in Havel-Hakimijevim algoritmom, predstavljene so nekatere lastnosti anihilacijskega števila in algoritem za iskanje le-tega. V tem delu je izpostavljena tudi povezava med anihilacijskim in neodvisnostnim številom grafa. Velja, da lahko neodvisnostno število navzgor omejimo z anihilacijskim številom. Ta meja je v nekaterih primerih natančnejša od drugih znanih mej.
V zadnjem poglavju je podrobneje obravnavana povezava med anihilacijskim in celotnim dominantnim številom. Postavljena je domneva, da lahko v vsakem netrivialnem grafu celotno dominantno število navzgor omejimo z anihilacijskim številom. V magistrskem delu bo ta domneva dokazana za grafe z najmanjšo stopnjo 3, cikle, drevesa, kaktus grafe in bločne grafe.
Ključne besede: anihilacijsko število, celotno dominantno število, neodvisnostno število, drevo, kaktus graf, bločni graf
Objavljeno v DKUM: 05.11.2019; Ogledov: 1031; Prenosov: 102
Celotno besedilo (730,62 KB) |
5. Neodvisna dominacija na grafihNina Črešnjevec, 2018, magistrsko delo Opis: V magistrskem delu obravnavamo različne tipe dominacij in sicer dominantno število, neodvisnostno število, neodvisno dominantno število in zgornje dominantno število. Neodvisno dominantno število je raziskano na različnih družinah grafov kot tudi na različnih grafovskih produktih.
V prvem delu magistrske naloge smo navedli vse pojme, trditve, izreke, ki jih potrebujemo za razumevanje glavnega problema magistrske naloge. Predstavimo tudi različne razrede grafov in različne dominacije v grafih.
V drugem poglavju obravnavamo različne meje neodvisnega dominantnega števila. Predstavljene so splošne meje, ki veljajo na različnih družinah grafov in meje, ki veljajo za dvodelne grafe.
Tretje poglavje pa se nanaša na neodvisno dominantno število krepkega, korenskega in kartezičnega produkta. Za nekatere od teh produktov smo prikazali tudi rezultate o neodvisnostnem številu in dominantnem številu.
Ključne besede: dominantno število, neodvisno dominantno število, neodvisnostno število, dominantno popolni grafi, dobro pokriti grafi, grafovski produkti
Objavljeno v DKUM: 13.07.2018; Ogledov: 1285; Prenosov: 134
Celotno besedilo (1,30 MB) |
6. O mavričnem dominantnem številuAnastazija Tacer, 2016, diplomsko delo Opis: V diplomskem delu ugotavljamo meje t-mavričnega dominantnega števila za poljuben graf.
Kadar je t = 3, govorimo o 3-mavrični dominantni funkciji. Pri označevanju vozlišč se omejimo na cikle (Cn), poti (Pn) in posplošene Petersenove grafe P(n,k). Zapišemo meje 3-mavričnega dominantnega števila za poti in cikle in nekatere posplošene Petersenove grafe.
Ključne besede: Mavrično dominantno število, mavrična dominantna funkcija, cikel, pot, posplošen Petersenov graf.
Objavljeno v DKUM: 10.03.2016; Ogledov: 2009; Prenosov: 116
Celotno besedilo (731,64 KB) |
7. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011, izvirni znanstveni članek Opis: Rimska dominacija je zgodovinsko utemeljena različica običajne dominacije, pri kateri vozlišča grafa označimo z oznakami iz množice ▫${0,1,2}$▫ tako, da ima vsako vozlišče z oznako 0 soseda z oznako 2. Najmanjšo izmed vsot oznak grafa imenujemo rimsko dominantno število grafa. Z uporabo algebraičnega pristopa dobimo konstantni algoritem za računanje rimskega dominantnega števila posebne vrste poligrafov: rota- in fasciagrafov. V posebnih primerih izračunamo formule za rimsko dominanto število kartezičnega produkta poti in ciklov ▫$P_n Box P_k$▫, ▫$P_n Box C_k$▫ za ▫$k leq 8$▫ in ▫$n in {mathbb N}$▫ ter za ▫$C_n Box P_k$▫ in ▫$C_n Box C_k$▫ za ▫$k leq 5$▫, ▫$n in {mathbb N}$▫. Dodan je seznam rimskih grafov med kartezičnimi produkti zgoraj omenjenih poti in ciklov.
Ključne besede: teorija grafov, kartezični produkt, rimsko dominantno število, poligrafi, algebra poti, graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Objavljeno v DKUM: 10.07.2015; Ogledov: 1762; Prenosov: 73
 Povezava na celotno besedilo |
8. Teguia, Alberto M.(1-DUKE); Godbole, Anant P.(1-ETNS): Sierpiński gasket graphs and some of their properties. (English summary). - Australas. J. Combin. 35 (2006), 181--192.Sandi Klavžar, 2007, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, dominantno število, Hamiltonova pot, mathematics, graph theory, Hamiltonian path, cycle structure, domination number, pebbling number
Objavljeno v DKUM: 10.07.2015; Ogledov: 1104; Prenosov: 18
Povezava na celotno besedilo |
9. El-Zahar, Mohamed H.(ET-ASHS); Shaheen, Ramy S.(SY-TISHS): Bounds for the domination number of toroidal grid graphs. (English summary). - J. Egyptian Math. Soc. 10 (2002), no. 2, 103--113.Sandi Klavžar, 2004, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, dominantno število, kartezični produkt, mathematics, graph theory, domination number, Cartesian product
Objavljeno v DKUM: 10.07.2015; Ogledov: 981; Prenosov: 56
Povezava na celotno besedilo |
10. Gravier, Sylvain: Total domination number of grid graphs. - Discrete Appl. Math. 121 (2002), no. 1-3, 119-128Sandi Klavžar, 2003, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, rešetke, dominantno število, mathematics, graph theory, grid graphs, total domination number
Objavljeno v DKUM: 10.07.2015; Ogledov: 1340; Prenosov: 30
Povezava na celotno besedilo |
