How long can one bluff in the domination game?

Boštjan Brešar (Author), Paul Dorbec (Author), Sandi Klavžar (Author), Gašper Košmrlj (Author)

Abstract

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.

Keywords

dominacijska igra;igralno dominantno število;grafi pretvarjanja;minus grafi;posplošeni Petersenovi grafi;Kneserjevi grafi;kartezični produkt grafov;Hammingovi grafi;domination game;game domination number;bluff graphs,;minus graphs;generalized Petersen graphs;Kneser graphs;Cartesian product of graphs;Hamming graphs;

Data

Language:	English
Year of publishing:	2017
Typology:	1.01 - Original Scientific Article
Organization:	UL FMF - Faculty of Mathematics and Physics
UDC:	519.17
COBISS:	17978457
ISSN:	1234-3099
Views:	809
Downloads:	395
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Kako dolgo se lahko pretvarjamo v dominacijski igri?
Secondary abstract:	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.
Secondary keywords:	dominacijska igra;igralno dominantno število;grafi pretvarjanja;minus grafi;posplošeni Petersenovi grafi;Kneserjevi grafi;kartezični produkt grafov;Hammingovi grafi;
URN:	URN:SI:UM:
Type (COBISS):	Scientific work
Pages:	str. 337-352
Volume:	ǂVol. ǂ37
Issue:	ǂno. ǂ2
Chronology:	2017
DOI:	10.7151/dmgt.1899
ID:	9608758