20.500.12556/DKUM-65601 How long can one bluff in the domination game? Kako dolgo se lahko pretvarjamo v dominacijski igri? The domination game is played on an arbitrary graph ▫$G$▫ by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. Minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs ▫$K(n,2)$▫, za ▫$n \ge 6$▫, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff. Dominacijsko igro na grafu ▫$G$▫ igrata dva igralca, Dominator in Zavlačevalka. Ko igro začenja Dominator, ji rečemo Igra 1, sicer pa Igra 2. V članku vpeljemo grafe pretvarjanja kot tiste grafe, v katerih je vsako vozlišče optimalno začetno vozlišče za Igro 1 in tudi za Igro 2. V tem članku je dokazano, da je vsak minus graf (to je graf, v katerem se Igra 2 konča hitreje kot Igra 1) tudi graf pretvarjanja. Predstavimo netrivialno neskončno družine minus grafov (in s tem tudi grafov pretvarjanja). Minus grafi z igralnim dominantnim številom enakim 3 so okarakterizirani. Vpeljemo tudi grafe dvojnega pretvarjanja in dokažemo, da so med njimi Kneserjevi grafi, ▫$K(n,2)$▫, za ▫$n \ge 6$▫. Dominacijsko igro obravnavamo tudi v posplošenih Petersenovih grafih in Hammingovih grafih. Odkrijemo več posplošenih Petersenovih grafov, ki so grafi pretvarjanja, niso pa vozliščno tranzitivni. Dokažemo, da Hammingov grafi niso grafi dvojnega pretvarjanja. domination game game domination number bluff graphs minus graphs generalized Petersen graphs Kneser graphs Cartesian product of graphs Hamming graphs dominacijska igra igralno dominantno število grafi pretvarjanja minus grafi posplošeni Petersenovi grafi Kneserjevi grafi kartezični produkt grafov Hammingovi grafi true true true University of Zielona Góra Angleški jezik Slovenski jezik Znanstveno delo 2017-05-09 15:18:30 2017-05-09 15:19:31 2026-01-13 11:41:20 2019-07-11 15:23:50 2017 0 0 Str. 337-352 št. 2 Letn. 37 2017 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2015-10-19 2016-01-07 0000-00-00 1234-3099 519.17 7487065 17978457 10.7151/dmgt.1899 1234-3099 URN:SI:UM:DK:DMQJPGXS Discussiones_Mathematicae_Graph_Theory_2017_Bresar_et_al._How_long_can_one_bluff_in_the_domination_game.pdf Discussiones_Mathematicae_Graph_Theory_2017_Bresar_et_al._How_long_can_one_bluff_in_the_domination_game.pdf 1 E2E21DDAD32086F0B202FAFD568E19EF 4d10c0562464cd2524e9bd53aba1784c14cace0aeb2ca861540d6675c1ecc080 1a539483-7c0e-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=111060 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1899 1 https://dk.um.si/Dokument.php?lang=slv&id=111059 Fakulteta za naravoslovje in matematiko 0 0 0