Domination game on paths and cycles - Košmrlj, Gašper (Ars mathematica contemporanea, 2017)
Dominacijska igra je igra za dva igralca, Dominatorja in Zavlačevalko, ki se odvija na enostavnem grafu. Igralca izmenično izbirata vozlišča, tako da v vsaki potezi izbereta vozlišče, ki v svoji zaprti okoli vsebuje vsaj eno še nedominirano vozlišče (tj. vozlišče, ki še ni bilo izbrano in ni sosednjo nobenemu izbranemu). Igra se konča, ko so vsa vozlišča dominirana in zato ni na voljo več nobene poteze. Dominator želi igro zaključiti čim hitreje, medtem ko Zavlačevalka želi ravno nasprotno, tj. končati igro v čim več potezah. Z ?$γ_g$? oziroma ?$γ_g'$? označujemo skupno število potez v igri, v kateri prvo potezo naredi Dominator oziroma Zavlačevalka in oba igralca igrata po svojih optimalnih strategijah. Avtorji Kinnersley et al. so v rokopisu iz leta 2012 izračunali vrednosti obeh invariant za poti in cikle, vendar rezultatov niso nikoli objavili. V tem članku dokažemo isti rezultat na povsem drugačen način. Še več, naš pristop nam poleg vrednosti invariant eksplicitno opiše tudi optimalni strategiji obeh igralcev.
Keywords: cikli; dominacijska igra; igralno dominacijsko število; poti