How Long Can One Bluff in the Domination Game?

Boštan Brešar, et al. "How Long Can One Bluff in the Domination Game?." Discussiones Mathematicae Graph Theory 37.2 (2017): 337-352. <http://eudml.org/doc/287997>.

@article{BoštanBrešar2017,
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), n ≥ 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.},
author = {Boštan Brešar, Paul Dorbec, Sandi Klavžar, Gašpar Košmrlj},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination game; game domination number; bluff graphs; minus graphs; generalized Petersen graphs; Kneser graphs; Cartesian product of graphs; Hamming graphs},
language = {eng},
number = {2},
pages = {337-352},
title = {How Long Can One Bluff in the Domination Game?},
url = {http://eudml.org/doc/287997},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Boštan Brešar
AU - Paul Dorbec
AU - Sandi Klavžar
AU - Gašpar Košmrlj
TI - How Long Can One Bluff in the Domination Game?
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 2
SP - 337
EP - 352
AB - 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), n ≥ 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.
LA - eng
KW - domination game; game domination number; bluff graphs; minus graphs; generalized Petersen graphs; Kneser graphs; Cartesian product of graphs; Hamming graphs
UR - http://eudml.org/doc/287997
ER -