246 KB22 KB200820252017Košmrlj, Gašperštevilka:1letnik:13str. 125-136COBISSID:17920857ISSN:1855-3966URN:URN:NBN:SI:doc-WQGLHOZKenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaciklidominacijska igraigralno dominacijsko številopotiDomination game on paths and cycles|Domination game is a game on a simple graph played by two players, Dominator and Staller who are alternating in taking turns. In each turn a player chooses a vertex in such a way that at least one new vertex gets dominated by this move. The game ends when all vertices are dominated, and thus no legal move is possible. As the names of the players suggest, Dominator tries to finish the game as fast as possible, while Staller wants to prolong its end as long as she can. By ?$\gamma_g$? ?$(\gamma_g^\prime)$? we denote the total number of moves in the game when Dominator (resp. Staller) starts, and both players play according to their optimal strategies. In a manuscript from 2012, Kinnersley et al. determined ?$\gamma_g $? and ?$\gamma_g^\prime$? for paths and cycles, but have not yet published this very important result. In this paper we give an alternative proof for these formulas. Our approach also explicitly describes optimal strategies for both playersDominacijska 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 ?$\gamma_g$? oziroma ?$\gamma_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 igralcevTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije