آمار
| تعداد نشریات | 5 |
| تعداد شمارهها | 112 |
| تعداد مقالات | 1,271 |
| تعداد مشاهده مقاله | 1,238,838 |
| تعداد دریافت فایل اصل مقاله | 1,098,293 |
Paired-Domination Game Played in Graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 2، دوره 4، شماره 2، اسفند 2019، صفحه 79-94 اصل مقاله (403.97 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2019.26437.1110 | ||
| نویسندگان | ||
| M.A. Henning* 1؛ Teresa W. Haynes2 | ||
| 1University of Johannesburg | ||
| 2East Tennessee State University; Department of Mathematics | ||
| چکیده | ||
| 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$. | ||
| کلیدواژهها | ||
| Paired-domination game؛ Paired-domination number؛ Domination game | ||
| مراجع | ||
|
[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.
| ||
|
آمار تعداد مشاهده مقاله: 1,094 تعداد دریافت فایل اصل مقاله: 830 |
||