Domination Game Critical Graphs

Csilla Bujtás; Sandi Klavžar; Gašper Košmrlj

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 781-796
  • ISSN: 2083-5892

Abstract

top
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 CnN of cycles. Along the way we determine γg(CnN) 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.

How to cite

top

Csilla Bujtás, Sandi Klavžar, and Gašper Košmrlj. "Domination Game Critical Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 781-796. <http://eudml.org/doc/276019>.

@article{CsillaBujtás2015,
abstract = {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 CnN of cycles. Along the way we determine γg(CnN) 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.},
author = {Csilla Bujtás, Sandi Klavžar, Gašper Košmrlj},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination number; domination game; domination game critical graphs; powers of cycles; trees},
language = {eng},
number = {4},
pages = {781-796},
title = {Domination Game Critical Graphs},
url = {http://eudml.org/doc/276019},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Csilla Bujtás
AU - Sandi Klavžar
AU - Gašper Košmrlj
TI - Domination Game Critical Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 781
EP - 796
AB - 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 CnN of cycles. Along the way we determine γg(CnN) 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.
LA - eng
KW - domination number; domination game; domination game critical graphs; powers of cycles; trees
UR - http://eudml.org/doc/276019
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, New York, 2008). doi:10.1007/978-1-84628-970-5[Crossref] 
  2. [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[Crossref][WoS] Zbl1295.05152
  3. [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[WoS][Crossref] Zbl1287.05088
  4. [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[Crossref][WoS] Zbl1223.05189
  5. [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[Crossref] Zbl0658.05042
  6. [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´em, Hungary, 73-78. 
  7. [7] Cs. Bujtás, Domination game on forests, Discrete Math. 338 (2015) 2220-2228. doi:10.1016/j.disc.2015.05.022[WoS][Crossref] 
  8. [8] Cs. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J. Combin. 22 (2015) #P3.29. 
  9. [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[Crossref] 
  10. [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[WoS][Crossref] Zbl1302.05117
  11. [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[Crossref][WoS] Zbl1285.05137
  12. [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[WoS][Crossref] Zbl1303.05136
  13. [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[Crossref] 
  14. [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. [15] M.A. Henning, O.R. Oellermann and H.C. Swart, Distance domination critical graphs, J. Combin. Math. Combin. Comput. 44 (2003) 33-45. Zbl1035.05064
  16. [16] S.R. Jayaram, Minimal dominating sets of cardinality two in a graph, Indian J. Pure Appl. Math. 28 (1997) 43-46. Zbl0871.05035
  17. [17] W.B. Kinnersley, D.B. West and R. Zamani, Game domination for grid-like graphs, manuscript, 2012. 
  18. [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[WoS][Crossref] Zbl1285.05123
  19. [19] G. Košmrlj, Realizations of the game domination number , J. Comb. Optim. 28 (2014) 447-461. doi:10.1007/s10878-012-9572-x[Crossref][WoS] Zbl1303.91051
  20. [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[Crossref][WoS] Zbl1298.05126
  21. [21] L. Lovász and M.D. Plummer, Matching Theory (AMS Chelsea Publishing, Providence, RI, 2009). 
  22. [22] W. Pegden, Critical graphs without triangles: an optimum density construction, Combinatorica 33 (2013) 495-513. doi:10.1007/s00493-013-2440-1[Crossref][WoS] Zbl06270640
  23. [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[Crossref][WoS] Zbl1145.05045
  24. [24] D.B. West, Introduction to Graph Theory (Prentice Hall, Inc., Upper Saddle River, NJ, 1996). Zbl0845.05001

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.