Geodesic
Domination Game Critical Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 781-796.

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

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γ_g (G), named the game domination number. Here we study the γ_g-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γ_g-critical graphs with γ_g = 2 and with γ_g = 3, moreover for each n we identify the (infinite) class of all γ_g-critical ones among the nth powers C_N^n of cycles. Along the way we determine γ_g ( C_N^n ) for all n and N. Results of a computer search for γ_g-critical trees are presented and several problems and research directions are also listed.
Keywords: domination number, domination game, domination game critical graphs, powers of cycles, trees 
@article{DMGT_2015_35_4_a14,
     author = {Bujt\'as, Csilla and Klav\v{z}ar, Sandi and Ko\v{s}mrlj, Ga\v{s}per},
     title = {Domination {Game} {Critical} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {781--796},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a14/}
}
TY  - JOUR
AU  - Bujtás, Csilla
AU  - Klavžar, Sandi
AU  - Košmrlj, Gašper
TI  - Domination Game Critical Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 781
EP  - 796
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a14/
LA  - en
ID  - DMGT_2015_35_4_a14
ER  - 
%0 Journal Article
%A Bujtás, Csilla
%A Klavžar, Sandi
%A Košmrlj, Gašper
%T Domination Game Critical Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 781-796
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a14/
%G en
%F DMGT_2015_35_4_a14
Bujtás, Csilla; Klavžar, Sandi; Košmrlj, Gašper. Domination Game Critical Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 781-796. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a14/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008). doi:10.1007/978-1-84628-970-5

[2] 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

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

[4] 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

[5] R.C. Brigham, P.Z. Chinn and R.D. Dutton, Vertex domination-critical graphs, Networks 1 (1988) 173-179. doi:10.1002/net.3230180304

[6] Cs. Bujtás, Domination game on trees without leaves at distance four, in: Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, A. Frank, A. Recski, G. Wiener, Eds., June 4-7 (2013) Veszprém, Hungary, 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] T. Burton and D.P. Summer, Domination dot-critical graphs, Discrete Math. 306 (2006) 11-18. doi:10.1016/j.disc.2005.06.029

[10] P. Dorbec, G. Košmrlj 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

[11] M. Furuya, Upper bounds on the diameter of domination dot-critical graphs with given connectivity, Discrete Appl. Math. 161 (2013) 2420-2426. doi:10.1016/j.dam.2013.05.011

[12] M. Furuya, The connectivity of domination dot-critical graphs with no critical ver- tices, Discuss. Math. Graph Theory 34 (2014) 683-690. doi:10.7151/dmgt.1752

[13] 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

[14] M.A. Henning, S. Klavžar and D.F. Rall, The 4/5 upper bound on the game total domination number, Combinatorica, to appear.

[15] M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs, J. Combin. Math. Combin. Comput. 44 (2003) 33-45.

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

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

[18] 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

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

[20] X. Li and B. Wei, Lower bounds on the number of edges in edge-chromatic-critical graphs with fixed maximum degrees, Discrete Math. 334 (2014) 1-12. doi:10.1016/j.disc.2014.06.017

[21] L. Lovász and M.D. Plummer, Matching Theory (AMS Chelsea Publishing, Providence, RI, 2009).

[22] W. Pegden, Critical graphs without triangles: an optimum density construction, Combinatorica 33 (2013) 495-513. doi:10.1007/s00493-013-2440-1

[23] F. Tian and FJ.-M. Xu, Distance domination-critical graphs, Appl. Math. Lett. 21 (2008) 416-420. doi:10.1016/j.aml.2007.05.013

[24] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996).