آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 117 |
| تعداد مقالات | 1,391 |
| تعداد مشاهده مقاله | 1,409,398 |
| تعداد دریافت فایل اصل مقاله | 1,376,514 |
Maker-Breaker domination game on Cartesian products of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 18 اسفند 1403 اصل مقاله (463.3 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.29866.2198 | ||
| نویسنده | ||
| Pakanun Dokyeesun* | ||
| Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia | ||
| چکیده | ||
| The Maker-Breaker domination game is played on a graph $G$ by two players, called Dominator and Staller. They alternately select an unplayed vertex in $G$. Dominator wins the game if he forms a dominating set while Staller wins the game if she claims all vertices from a closed neighborhood of a vertex. The game is called D-game if Dominator starts the game and it is an \emph{S-game} when Staller starts the game. If Dominator is the winner in the D-game (or the S-game), then $\gamma_{MB}(G)$ (or $\gamma_{MB}^{\prime}(G)$) is defined by the minimum number of moves of Dominator to win the game under any strategy of Staller. Analogously, when Staller is the winner, $\gamma_{SMB}(G)$ and $\gamma_{SMB}^{\prime}(G)$ can be defined in the same way. We determine the winner of the game on the Cartesian product of paths, stars, and complete bipartite graphs, and how fast the winner wins. We prove that Dominator is the winner on $P_m \square P_n$ in both the D-game and the S-game, and $\gamma_{MB}(P_m \square P_n)$ and $\gamma_{MB}^{\prime}(P_m \square P_n)$ are determined when $m=3$ and $3 \le n \le 5$. Dominator also wins on $G \square H$ in both games if $G$ and $H$ admit nontrivial path covers. Furthermore, we establish the winner in the D-game and the S-game on $K_{m,n} \square K_{m',n'}$ for every positive integers $m, m',n,n'$. We prove the exact formulas for $\gamma_{MB}(G)$, $\gamma_{MB}^{\prime}(G)$, $\gamma_{SMB}(G)$, and $\gamma_{SMB}^{\prime}(G)$ where $G$ is a product of stars. | ||
| کلیدواژه‌ها | ||
| domination game؛ Maker-Breaker game؛ Maker-Breaker domination game؛ hypergraph؛ Cartesian product of graphs | ||
| مراجع | ||
|
[1] J. Beck, On positional games, J. Combin. Theory Ser. A 30 (1981), no. 2, 117–133. https://doi.org/10.1016/0097-3165(81)90001-7
[2] C. Berge, Hypergraphs: Combinatorics of Finite Sets, North Holland, 1989.
[3] B. Brešar, M.A. Henning, S. Klavžar, and D.F. Rall, Domination Games Played on Graphs, Springer, 2021.
[4] B. Brešar, S. žar, and D.F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010), no. 3, 979–991. https://doi.org/10.1137/100786800
[5] C. Bujtás and P. Dokyeesun, Fast winning strategies for Staller in the Maker–Breaker domination game, Discrete Appl. Math. 344 (2024), 10–22. https://doi.org/10.1016/j.dam.2023.11.015
[6] C. Bujtás, P. Dokyeesun, and S. Klavžar, Maker-Breaker domination game on trees when Staller wins, Discrete Math. Theor. Comput. Sci. 25 (2023), no. 2, #12 https://doi.org/10.46298/dmtcs.10515
[7] E. Duchene, V. Gledel, A. Parreau, and G. Renault, Maker–Breaker domination game, Discrete Math. 343 (2020), no. 9, Article ID: 111955. https://doi.org/10.1016/j.disc.2020.111955
[8] P. Erdös and J.L. Selfridge, On a combinatorial game, J. Combin. Theory Ser. A 14 (1973), no. 3, 298–301. https://doi.org/10.1016/0097-3165(73)90005-8
[9] J. Forcan and M. Mikalački, Maker-Breaker total domination game on cubic graphs, Discrete Math. Theor. Comput. Sci. 24 (2022), no. 1, #20 https://doi.org/10.46298/dmtcs.8529
[10] J. Forcan and J. Qi, Maker-Breaker domination number for Cartesian products of path graphs P2 and Pn, Discrete Math. Theor. Comput. Sci. 25 (2024), no. 2, #23 https://doi.org/10.46298/dmtcs.10465
[11] V. Gledel, M.A. Henning, V. Iršič, and S. Klavžar, Maker–Breaker total domination game, Discrete Appl. Math. 282 (2020), 96–107. https://doi.org/10.1016/j.dam.2019.11.004
[12] V. Gledel, V. Iršič, and S. Klavžar, Maker–Breaker domination number, Bull. Malays. Math. Sci. Soc. 42 (2019), no. 4, 1773–1789. https://doi.org/10.1007/s40840-019-00757-1
[13] D. Hefetz, M. Krivelevich, M. Stojaković, and T. Szabó, Positional Games, Springer, 2014.
[14] M.S. Jacobson and L.F. Kinch, On the domination number of products of graphs: I, Ars. Combin. 18 (1983), 33–44.
[15] 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. https://doi.org/10.1137/120884742
[16] L. Lovász, Subgraphs with prescribed valencies, J. Combin. Theory 8 (1970), no. 4, 391–416. https://doi.org/10.1016/S0021-9800(70)80033-3 | ||
|
آمار تعداد مشاهده مقاله: 119 تعداد دریافت فایل اصل مقاله: 83 |
||