Geodesic
How Long Can One Bluff in the Domination Game?
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 337-352.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs 
@article{DMGT_2017_37_2_a2,
     author = {Bre\v{s}ar, Bo\v{s}tan and Dorbec, Paul and Klav\v{z}ar, Sandi and Ko\v{s}mrlj, Ga\v{s}par},
     title = {How {Long} {Can} {One} {Bluff} in the {Domination} {Game?}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {337--352},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a2/}
}
TY  - JOUR
AU  - Brešar, Boštan
AU  - Dorbec, Paul
AU  - Klavžar, Sandi
AU  - Košmrlj, Gašpar
TI  - How Long Can One Bluff in the Domination Game?
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 337
EP  - 352
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a2/
LA  - en
ID  - DMGT_2017_37_2_a2
ER  - 
%0 Journal Article
%A Brešar, Boštan
%A Dorbec, Paul
%A Klavžar, Sandi
%A Košmrlj, Gašpar
%T How Long Can One Bluff in the Domination Game?
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 337-352
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a2/
%G en
%F DMGT_2017_37_2_a2
Brešar, Boštan; Dorbec, Paul; Klavžar, Sandi; Košmrlj, Gašpar. How Long Can One Bluff in the Domination Game?. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 337-352. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a2/

[1] B. Brešar, P. Dorbec, S. Klavžar and G. Košmrlj, Domination game: Effect of edge- and vertex-removal, Discrete Math. 330 (2014) 1-10. doi: 10.1016/j.disc.2014.04.015

[2] B. Brešar, T. Gologranc, M. Milanič, D.F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014) 22-36. doi: 10.1016/j.disc.2014.07.016

[3] B. Brešar, S. Klavžar, G. Košmrlj and D.F. Rall, Domination game: extremal fam- ilies of graphs for the 3/5-conjectures, Discrete Appl. Math. 161 (2013) 1308-1316. doi: 10.1016/j.dam.2013.01.025

[4] B. Brešar, S. Klavžar, G. Košmrlj and D.F. Rall, Guarded subgraphs and the domi- nation game, Discrete Math. Theor. Comput. Sci. 17 (2015) 161-168.

[5] B. Brešar, S. Klavžar and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991. doi: 10.1137/100786800 `

[6] Cs. Bujtás, Domination game on trees without leaves at distance four, in: A. Frank, A. Recski and G. Wiener (Eds.), Proceedings of the 8th Japanese-Hungarian Sym- posium on Discrete Mathematics and Its Applications (Veszprém, Hungary, 2013), 73-78.

[7] Cs. Bujtás, Domination game on forests, Discrete Math. 338 (2015) 2220-2228. doi: 10.1016/j.disc.2015.05.022

[8] Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015) #P3.29.

[9] Cs. Bujtás and S. Klavžar, Improved upper bounds on the domination number of graphs with minimum degree at least five, Graphs Combin. 32 (2016) 511-519. doi: 10.1007/s00373-015-1585-7

[10] Cs. Bujtás, S. Klavžar and G. Košmrlj, Domination game critical graphs, Discuss. Math. Graph Theory 35 (2015) 781-796. doi: 10.7151/dmgt.1839

[11] Cs. Bujtás and Z. Tuza, The disjoint domination game, Discrete Math. 339 (2016) 1985-1992. doi: 10.1016/j.disc.2015.04.028

[12] P. Dorbec, G. Koˇsmrlj and G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015) 71-79. doi: 10.1016/j.disc.2014.08.024

[13] R. Frucht, J.E. Graver and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211-218. doi: 10.1017/S0305004100049811

[14] I. Gorodezky, Dominating Sets in Kneser Graphs (Master Thesis, University of Waterloo, 2007).

[15] M.A. Henning and W.B. Kinnersley, Domination game: A proof of the 3/5-conject- ure for graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016) 20-35. doi: 10.1137/140976935

[16] M.A. Henning, S. Klavžar and D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015) 1453-1462. doi: 10.1007/s00373-014-1470-9

[17] M.A. Henning, S. Klavžar and D.F. Rall, The 4/5 upper bound on the game total do- mination number, Combinatorica, to appear. doi: 10.1007/s00493-015-3316-3

[18] S.R. Jayaram, Minimal dominating sets of cardinality two in a graph, Indian J. Pure Appl. Math. 28 (1997) 43-46.

[19] W.B. Kinnersley, D.B. West and R. Zamani, Game domination for grid-like graphs, unpublished manuscript (2012).

[20] W.B. Kinnersley, D.B.West and R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013) 2090-2107. doi: 10.1137/120884742

[21] G. Košmrlj, Realizations of the game domination number, J. Comb. Optim. 28 (2014) 447-461. doi: 10.1007/s10878-012-9572-x

[22] M.J. Nadjafi-Arani, M. Siggers and H. Soltani, Characterisation of forests with triv- ial game domination numbers, J. Comb. Optim. 32 (2016) 800-811. doi: 10.1007/s10878-015-9903-9

[23] S. Schmidt, The 3/5-conjecture for weakly S(K1,3)-free forests, arXiv:1507.02875v1 [math.CO] (2015).