20.500.12556/DKUM-65335 Domination game critical graphs Kritični grafi za dominacijsko igro The domination game is played on a graph ▫$G$▫ by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on ▫$G$▫ and both players play optimally is the graph invariant ▫$\gamma_g(G)$▫, named the game domination number. Here we study the ▫$\gamma_g$▫-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize ▫$\gamma_g$▫-critical graphs with ▫$\gamma_g =2$▫ and with ▫$\gamma_g =3$▫, moreover for each ▫$n$▫ we identify the (infinite) class of all ▫$\gamma_g$▫-critical ones among the ▫$n$▫th powers ▫$C_N^n$▫ of cycles. Along the way we determine ▫$\gamma_g(C_N^n)$▫ for all ▫$n$▫ and ▫$N$▫. Results of a computer search for ▫$\gamma_g$▫-critical trees are presented and several problems and research directions are also listed. Dominacijsko igro na grafu ▫$G$▫ igrata dva igralca, ki izmenično izbirata vozlišča grafa tako, da je po vsaki potezi dominirano vsaj eno novo vozlišče. Igra se zaključi, ko so vsa vozlišča dominirana. Eden od igralcev - Dominator - želi igro končati čim hitreje, medtem ko Zavlačevalka želi igro končati čim kasneje. Število potez v igri, ki jo začne Dominator, in ko oba igralca igrata optimalno, imenujemo igralno dominacijsko število in označimo z ▫$\gamma_g(G)$▫. V članku raziskujemo ▫$\gamma_g$▫-kritične grafe, ki so vpeljani kot grafi kritični glede na predhodno dominacijo vozlišča. Poleg nekaj splošnih rezultatov karakteriziramo ▫$\gamma_g$▫-kritične grafe z ▫$\gamma_g =2$▫ in z ▫$\gamma_g =3$▫. Za vsak $n$ tudi identificiramo neskončen razred grafov vseh ▫$\gamma_g$▫-kritičnih grafov izmed ▫$n$▫tih potenc ▫$C_N^n$▫ ciklov. Pri tem določimo ▫$\gamma_g(C_N^n)$▫ za vse ▫$n$▫ in ▫$N$▫. Predstavljeni so rezultati računalniškega pregledovanja ▫$\gamma_g$▫-kritičnih dreves. Navedenih je tudi več problemov in možnih nadaljnjih raziskovalnih smeri. domination game domination game critical graphs powers of cycles trees dominacijska igra kritični grafi za dominacijsko igro potence ciklov drevesa true true true Angleški jezik Slovenski jezik Znanstveno delo 2017-03-31 10:06:44 2017-03-31 10:07:45 2025-10-01 09:10:41 2019-07-11 15:14:56 0 0 0 str. 781-796 št. 4 Letn. 35 2015 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2024-08-31 2025-02-20 2025-02-28 1234-3099 519.17 7487065 17464921 1234-3099 URN:SI:UM:DK:D0MNDQWR Discussiones_Mathematicae_Graph_Theory_2015_Bujtas,_Klavzar,_Kosmrlj_Domination_game_critical_graphs.pdf Discussiones_Mathematicae_Graph_Theory_2015_Bujtas,_Klavzar,_Kosmrlj_Domination_game_critical_graphs.pdf 1 F52741DC9E1C4954DB3E246A85FD7EC7 af27660d90b7f1c9f84b144c4d86a6f4bed407e200f61b22c4a5d995679095cc 0b4936b8-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=110394 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1839 1 https://dk.um.si/Dokument.php?lang=slv&id=110393 Fakulteta za naravoslovje in matematiko 0 0 0