Raziskovana je nedavno vpeljana celotna igra dominacije. To igro igrata na grafu $G$ dva igralca, ki sta poimenovana Dominator in Zavlačevalka. Igralca izmenoma izbirata vozlišča grafa tako, da vsako izbrano vozlišče celotno dominira vsaj eno vozlišče, ki ni bilo celotno dominirano s prej izbranimi vozlišči. Dominatorjev cilj je kar se da hitro celotno dominirati graf graf $G$, medtem ko želi Zavlačevalka kar se da zakasniti ta postopek. Celotno igralno dominacijsko število $\gamma_{tg}(G)$ grafa $G$ je število potez, ki jih opravita igralca, če igro začne Dominator in oba igralca igrata optimalno. Kadar Zavlačevalka začne igro, ustrezno invarianto označimo z $\gamma_{tg}'(G)$. V članku je dokazano, da če je $G$ graf na $n$ vozliščih, v katerem vsaka komponenta vsebuje vsaj tri vozlišča, potem velja $\gamma_{tg}(G) \le 4n/5$ in $\gamma_{tg}'(G) \le (4n+2)/5$. Kot posledico tega rezultata dobimo tudi zgornji meji za obe igri na grafih, ki so brez izoliranih vozlišč.
COBISS.SI-ID: 18018137
Najdaljše zaporedje $S$ različnih vozlišč grafa $G$, v katerem vsako vozlišče dominira vsaj eno vozlišče, ki ni dominirano z vozlišči pred njim, se imenuje Grundyjevo dominacijsko zaporedje. Dolžina takšnega zaporedja je Grundyjevo dominantno število grafa $G$. V članku študiramo Grundyjevo dominantno število štirih standardnih produktov grafov: kartezičnega, leksikografskega, direktnega in krepkega produkta. Za vsakega od njih predstavimo spodnjo mejo za Grundyjevo dominantno število, ki se izkaže natančna za leksikografski produkt. Domnevamo tudi, da je točna za krepki produkt. V večini primerov je določeno Grundyjevo dominantno število za produkte poti in/ali ciklov.
COBISS.SI-ID: 17829465
Nadaljujemo z raziskavami Grundyjevega dominantnega števila grafa. Predstavimo linearen algoritem za določitev Grundyjevega dominantnega števila grafa intervalov. Dokažemo točno vrednost Grundyjevega dominantega števila poljubnega grafa Sierpińskega in predstavimo učinkovit algoritem za konstrukcijo pripadajočih zaporedij. Te rezultate dobimo z uporabo ostrih mej za Grundyjevo dominantno število podgrafa, dobljenega z odstranitvijo vozlišča ali povezave, ki jih dokažemo v članku.
COBISS.SI-ID: 17807705
Če je $G$ graf, potem je zaporedje vozlišč $v_1,\dots,v_m$ zaporedje zaprtih okolic, če za vse $2\le i \le m$ velja $N[v_i]\not\subseteq \cup_{j=1}^{i-1}N[v_j]$ in je zaporedje odprtih okolic, če za vse $2\le i \le m$ velja $N(v_i)\not\subseteq \cup_{j=1}^{i-1}N(v_j)$. Dolžina najdaljšega zaporedja zaprtih (odprtih) okolic je Grundyjevo (Grundyjevo celotno) dominantno število grafa $G$. V tem članku vpeljemo dva podobna koncepta, v katerih je zahteva za soseščine spremenjena v $N(v_i)\not\subseteq \cup_{j=1}^{i-1}N[v_j]$ ali v $N[v_i]\not\subseteq \cup_{j=1}^{i-1}N(v_j)$. V prvem primeru vzpostavimo močno povezavo s številom ničelne prisile grafa, medtem ko v drugem primeru določimo računsko zahtevnost odločitvenega problema. Raziskujemo tudi razmerja med vsemi štirimi koncepti in razpravljamo o njihovih računskih zahtevnostih.
COBISS.SI-ID: 18163289
V teorijo dominacijske igre sta vpeljani dve novi tehniki. Lema o prerezu omeji igralno dominacijsko število delno dominiranega grafa z igralnim dominacijskim številom ustrezno preoblikovanih delno dominiranih grafov. Lema o uniji omeji S-igralno dominacijsko število disjunktne unije poti z uporabo ustreznih utežnih funkcij. S pomočjo teh dveh orodij je dokazana prej postavljena domneva, ki pravi, da so t.i. pajki s tremi nogami kritični grafi za dominacijsko igro. Izpeljana je tudi razširjenalema o prerezu. Prikazana so vsa drevesa na 18, 19 in 20 vozliščih,ki so kritična za dominacijsko igro.
COBISS.SI-ID: 18544729