آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,450 |
| تعداد مشاهده مقاله | 1,563,786 |
| تعداد دریافت فایل اصل مقاله | 1,465,236 |
Builder-Blocker general position games | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 10، دوره 11، شماره 2، شهریور 2026، صفحه 465-486 اصل مقاله (462.09 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2024.29122.1854 | ||
| نویسندگان | ||
| Sandi Klavžar1، 2، 3؛ Jing Tian4، 2؛ James Tuite* 5 | ||
| 1Faculty of Mathematics and Physics, University of Ljubljana, Slovenia | ||
| 2Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia | ||
| 3Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia | ||
| 4School of Science, Zhejiang University of Science and Technology, Hangzhou, Zhejiang 310023, P.R. China | ||
| 5School of Mathematics and Statistics, Open University, Milton Keynes, UK | ||
| چکیده | ||
| This paper considers a game version of the general position problem in which a general position set is built through adversarial play. Two players in a graph, Builder and Blocker, take it in turns to add a vertex to a set, such that the vertices of this set are always in general position. The goal of Builder is to create a large general position set, whilst the aim of Blocker is to frustrate Builder's plans by making the set as small as possible. The game finishes when no further vertices can be added without creating three-in-a-line and the number of vertices in this set is the game general position number. We determine this number for some common graph classes and provide sharp bounds, in particular for the case of trees. We also discuss the effect of changing the order of the players. | ||
| کلیدواژهها | ||
| general position set؛ games on graphs؛ trees؛ no-three-in-line؛ universal line | ||
| مراجع | ||
|
[1] B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar, and E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019), 84–89. https://doi.org/10.1016/j.amc.2019.04.064
[2] T. Bartnicki, J. Grytczuk, H.A. Kierstead, and X. Zhu, The map-coloring game, Am. Math. Mon. 114 (2007), no. 9, 793–803. https://doi.org/10.1080/00029890.2007.11920471
[3] A. Bondy and U.S.R. Murty, Graph Theory, Springer London, 2009.
[4] B. Brešar, M.A. Henning, S. Klavžar, and D.F. Rall, Domination Games Played on Graphs, Springer Cham, 2021.
[5] 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. https://doi.org/10.1137/100786800
[6] U. Chandran S.V., S. Klavžar, P.K. Neethu, and R. Sampaio, The general position avoidance game and hardness of general position games, Theor. Comput. Sci. 988 (2024), Article ID: 114370. https://doi.org/10.1016/j.tcs.2023.114370
[7] U. Chandran S.V. and G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Comb. 4 (2016), 135–143.
[8] G. Di Stefano, S. Klavžar, A. Krishnakumar, J. Tuite, and I. Yero, Lower general position sets in graphs, Discuss. Math. Graph Theory (2024), In press. https://doi.org/10.7151/dmgt.2542
[9] H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917.
[10] P. Erdös and J.L. Selfridge, On a combinatorial game, J. Comb. Theory Ser. A. 14 (1973), no. 3, 298–301. https://doi.org/10.1016/0097-3165(73)90005-8
[11] M. Gardner, Mathematical games, Sci. Am. 222 (1970), no. 6, 132–140.
[12] M. Gardner, Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer, Sci. Am. 235 (1976), no. 4, 131–137.
[13] M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar, and G. Rus, The general position problem on kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021), no. 4, 1199–1213. http://doi.org/10.7151/dmgt.2269
[14] V. Iršič, S. Klavžar, G. Rus, and J. Tuite, General position polynomials, Results Math. 79 (2024), no. 3, Article number: 110. https://doi.org/10.1007/s00025-024-02133-3
[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] S. Klavžar, A. Krishnakumar, J. Tuite, and I.G. Yero, Traversing a graph in general position, Bull. Aust. Math. Soc. 108 (2023), no. 3, 353–365. https://doi.org/10.1017/S0004972723000102
[17] S. Klavžar, P.K. Neethu, and U. Chandran S.V., The general position achievement game played on graphs, Discrete Appl. Math. 317 (2022), 109–116. https://doi.org/10.1016/j.dam.2022.04.019
[18] S. Klavžar and E. Tan, Edge general position sets in fibonacci and lucas cubes, Bull. Malays. Math. Sci. Soc. 46 (2023), no. 4, Article number: 120. https://doi.org/10.1007/s40840-023-01517-y
[19] D. Korže and A. Vesel, General position sets in two families of Cartesian product graphs, Mediterr. J. Math. 20 (2023), no. 4, Article number: 203. https://doi.org/10.1007/s00009-023-02416-z
[20] P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018), no. 2, 177–187. https://doi.org/10.1017/S0004972718000473 [21] P. Manuel, R. Prabha, and S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022), no. 6, 2997–3009. https://doi.org/10.1007/s40840-022-01319-8
[22] B. Patkós, On the general position problem on Kneser graphs, Ars. Math. Contemp. 18 (2020), no. 2, 273–280. https://doi.org/10.26493/1855-3974.1957.a0f
[23] J.A. Rodriguez-Velázquez, Universal lines in graphs, Quaest. Math. 45 (2022), no. 10, 1485–1500. https://doi.org/10.2989/16073606.2021.1950862
[24] E.J. Thomas, U. Chandran S.V., J. Tuite, and G. Di Stefano, On monophonic position sets in graphs, Discrete Appl. Math. 354 (2024), 72–82. https://doi.org/10.1016/j.dam.2023.02.021
[25] E.J. Thomas, U. Chandran S.V., J. Tuite, and G. Di Stefano, On the general position number of Mycielskian graphs, Discrete Appl. Math. 353 (2024), 29–43. https://doi.org/10.1016/j.dam.2024.03.015
[26] J. Tian and K. Xu, The general position number of Cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021), Article ID: 126206. https://doi.org/10.1016/j.amc.2021.126206
[27] Y. Yao, M. He, and S. Ji, On the general position number of two classes of graphs, Open Math. 20 (2022), no. 1, 1021–1029. https://doi.org/10.1515/math-2022-0444 | ||
|
آمار تعداد مشاهده مقاله: 317 تعداد دریافت فایل اصل مقاله: 339 |
||