How long can one bluff in the domination game?

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Angleški jezik
Leto izida:	2017
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	17978457
ISSN:	1234-3099
Št. ogledov:	809
Št. prenosov:	395
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Kako dolgo se lahko pretvarjamo v dominacijski igri?
Sekundarni povzetek:	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.
Sekundarne ključne besede:	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:
Vrsta dela (COBISS):	Znanstveno delo
Strani:	str. 337-352
Letnik:	ǂVol. ǂ37
Zvezek:	ǂno. ǂ2
Čas izdaje:	2017
DOI:	10.7151/dmgt.1899
ID:	9608758