1. Super dominantno število grafaTajda Remic, 2024, master's thesis Abstract: 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. Keywords: super dominantno število, super dominantna množica, drevo, neodvisnostno število, dominantno število, prirejanje Published in DKUM: 11.06.2024; Views: 153; Downloads: 34 Full text (6,92 MB) |
2. Meje za mavrična dominantna števila : magistrsko deloKlavdija Zelko, 2023, master's thesis Abstract: 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. Keywords: graf, dominantno število, mavrična dominantna funkcija, mavrično dominantno število Published in DKUM: 02.02.2023; Views: 766; Downloads: 55 Full text (3,91 MB) |
3. Grafi, ki dosežejo enakost v vizingovi domnevi : magistrsko deloAnamarija Lakner, 2022, master's thesis Abstract: 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. Keywords: dominantno število, dominantna množica, Vizingova domneva, enakost v Vizingovi domnevi Published in DKUM: 28.10.2022; Views: 573; Downloads: 50 Full text (568,89 KB) |
4. Anihilacijsko število grafa in njegova povezava s celotnim dominantnim številomLara Lužnic, 2019, master's thesis Abstract: 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. Keywords: anihilacijsko število, celotno dominantno število, neodvisnostno število, drevo, kaktus graf, bločni graf Published in DKUM: 05.11.2019; Views: 1031; Downloads: 102 Full text (730,62 KB) |
5. Neodvisna dominacija na grafihNina Črešnjevec, 2018, master's thesis Abstract: 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. Keywords: dominantno število, neodvisno dominantno število, neodvisnostno število, dominantno popolni grafi, dobro pokriti grafi, grafovski produkti Published in DKUM: 13.07.2018; Views: 1285; Downloads: 134 Full text (1,30 MB) |
6. O mavričnem dominantnem številuAnastazija Tacer, 2016, undergraduate thesis Abstract: 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. Keywords: Mavrično dominantno število, mavrična dominantna funkcija, cikel, pot, posplošen Petersenov graf. Published in DKUM: 10.03.2016; Views: 2009; Downloads: 117 Full text (731,64 KB) |
7. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011, original scientific article Abstract: 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. Keywords: teorija grafov, kartezični produkt, rimsko dominantno število, poligrafi, algebra poti, graph theory, Roman domination number, Cartesian product, polygraphs, path algebra Published in DKUM: 10.07.2015; Views: 1762; Downloads: 73 Link to full text |
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, review, book review, critique Keywords: matematika, teorija grafov, dominantno število, Hamiltonova pot, mathematics, graph theory, Hamiltonian path, cycle structure, domination number, pebbling number Published in DKUM: 10.07.2015; Views: 1104; Downloads: 18 Link to full text |
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, review, book review, critique Keywords: matematika, teorija grafov, dominantno število, kartezični produkt, mathematics, graph theory, domination number, Cartesian product Published in DKUM: 10.07.2015; Views: 981; Downloads: 56 Link to full text |
10. Gravier, Sylvain: Total domination number of grid graphs. - Discrete Appl. Math. 121 (2002), no. 1-3, 119-128Sandi Klavžar, 2003, review, book review, critique Keywords: matematika, teorija grafov, rešetke, dominantno število, mathematics, graph theory, grid graphs, total domination number Published in DKUM: 10.07.2015; Views: 1340; Downloads: 30 Link to full text |