Paired-Domination Game Played in Graphs

Document Type : Original paper

Authors

1 University of Johannesburg

2 East Tennessee State University; Department of Mathematics

Abstract

In this paper, we continue the study of the domination game in graphs introduced by Bre{\v{s}}ar, Klav{\v{z}}ar, and Rall [SIAM J. Discrete Math. 24 (2010) 979--991]. We study the paired-domination version of the domination game which adds a matching dimension to the game. This game is played on a graph $G$ by two players, named Dominator and Pairer. They alternately take turns choosing vertices of $G$ such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of $G$; that is, a dominating set in $G$ that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number $\gamma_{pr}(G)$ of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Let $G$ be a graph on $n$ vertices with minimum degree at least~$2$. We show that $\gamma_{pr}(G) \le \frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $\gamma_{pr}(G) \le \frac{3}{4}n$, where a graph is $(C_4,C_5)$-free if it has no induced $4$-cycle or $5$-cycle. If $G$ is $2$-connected and bipartite or if $G$ is $2$-connected and the sum of every two adjacent vertices in $G$ is at least~$5$, then we show that  $\gamma_{pr}(G) \le \frac{3}{4}n$.

Keywords

Main Subjects

References

[1] H.L. Bodlaender, On the complexity of some coloring games, Internat. J. Found. Comp. Sci. 2 (1991), no. 2, 133–147.
[2] A. Bonato, W.B. Kinnersley, and P. Pra lat, Game toppling number for complete and random graphs, Discrete Math. Theor. Comp. Sci. 16 (2014), 229–252.
[3] M. Borowiecki, E. Sidorowicz, and Zs. Tuza, Game list colouring of graphs, Electron. J. Combin. 14 (2007), #R26, 11 pages.
[4] 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.
[5] B. Brešar and M.A. Henning, The game total domination problem is log-complete in pspace, Inform. Process. Lett. 126 (2017), 12–17.
[6] B. Brešar, S. Klavžar, G. Košmrlj, and D.F. Rall, Domination game: Extremal families of graphs for $\frac{3}{5}$-conjectures, Discrete Appl. Math. 161 (2013), no. 10-11, 1308–1316.
[7] B. Brešar, S. Klavžar, and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), no. 3, 979–991.
[8] B. Brešar, S. Klavžar, and D.F. Rall, Domination game played on trees and spanning subgraphs, Discrete Math. 313 (2013), no. 8, 915–923.
[9] C. Bujtás, Domination game on trees without leaves at distance four, Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, Veszpr´em, 2013, pp. 4–7.
[10] C. Bujtás, M.A. Henning, and Z. Tuza, Transversal game on hypergraphs and the $\frac{3}{4}$-conjecture on the total domination game, SIAM J. Discrete Math. 30 (2016), no. 3, 1830–1847.
[11] C. Bujtás, M.A. Henning, and Z. Tuza, Bounds on the game transversal number in hypergraphs, European J. Combin. 59 (2017), 34–50.
[12] C. Bujtás and Z. Tuza, The disjoint domination game, Discrete Math. 339 (2016), no. 7, 1985–1992.
[13] J. Butterfield, T. Grauman, W.B. Kinnersley, K.G. Milans, C. Stocker, and D.B. West, On-line ramsey theory for bounded degree graphs, Electron. J. Combin. 18 (2011), #P136.
[14] D.W. Cranston, W.B. Kinnersley, O. Suil, and D.B. West, Game matching number of graphs, Discrete Appl. Math. 161 (2013), no. 13-14, 1828–1836.
[15] W.J. Desormeaux and M.A. Henning, Paired domination in graphs: A survey and recent results, Util. Math. 94 (2014), 101–166.
[16] P. Dorbec and M.A. Henning, Game total domination for cycles and paths, Discrete Appl. Math. 208 (2016), 7–18.
[17] P. Dorbec, G. Košmrlj, and G. Renault, The domination game played on unions of graphs, Discrete Math. 338 (2015), no. 1, 71–79.
[18] M. Gardner, Mathematical games, Scientific American 244 (1981), 18–26.
[19] W. Goddard and M.A. Henning, The matcher game played in graphs, Discrete Appl. Math. 237 (2018), 82–88.
[20] J.A. Grytczuk, M. Ha luszczak, and H.A. Kierstead, On-line ramsey theory, Electron. J. Combin. 11 (2004), #R57, 11 pages.
[21] J.A. Grytczuk, H.A. Kierstead, and P. Pralat, On-line ramsey numbers for paths and stars, Discrete Math. Theor. Comp. Sci. 10 (2008), no. 3, 63–75.
[22] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[23] T.W. Haynes and P.J. Slater, Paired-domination in graphs, Networks 32 (1998), no. 3, 199–206.
[24] M.A. Henning and W.B. Kinnersley, Domination game: A proof of the $\frac{3}{5}$-conjecture for graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016), no. 1, 20–35.
[25] M.A. Henning and S. Klavžar, Infinite families of circular and mőbius ladders that are total domination game critical, Bull. Malays. Math. Sci. Soc. 41 (2018), no. 4, 2141–2149.
[26] M.A. Henning, S. Klavžar, and D.F. Rall, Total version of the domination game, Graphs Combin. 31 (2015), no. 5, 1453–1462. 
[27] M.A. Henning, S. Klavžar, The $\frac{4}{5}$ upper bound on the game total domination number, Combinatorica
37 (2017), no. 2, 223–251.
[28] M.A. Henning and D.F. Rall, Progress towards the total domination game $\frac{3}{4}$-conjecture, Discrete Math. 339 (2016), no. 11, 2620–2627.
[29] M.A. Henning and D.F. Rall, Trees with equal total domination and game total domination numbers,
Discrete Appl. Math. 226 (2017), 58–70.
[30] M.A. Henning, I. Schiermeyer, and A. Yeo, A new bound on the domination number of graphs with minimum degree two, Electronic J. Combin. 18 (2011), #P12.
[31] M.A. Henning and A. Yeo, Total Domination in Graphs, Springer, 2013. 
[32] W.B. Kinnersley, D.B. West, and R. Zamani, Extremal problems for game domination number, SIAM J. Discrete Math. 27 (2013), no. 4, 2090–2107.
[33] G. Košmrlj, Realizations of the game domination number, J. Combin. Optim. 28 (2014), no. 2, 447–461.
[34] W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989), no. 6, 749–762.
[35] U. Schauz, Mr. paint and mrs. correct, Electron. J. Combin. 16 (2009), #R77, 18 pages.
[36] Z. Tuza and X. Zhu, Colouring games. chapter 13 in: Topics in chromatic graph theory (l. w. beineke and r. j. wilson, eds.), encyclopedia of mathematics and its applications, vol. 156, Cambridge University Press, 304–326, 2014.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 79-94

Files

Share

How to cite

Statistics