Builder-Blocker general position games

Articles in Press

Document Type : Original paper

Authors

1 Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

2 Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

3 Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

4 School of Science, Zhejiang University of Science and Technology, Hangzhou, Zhejiang 310023, P.R. China

5 School of Mathematics and Statistics, Open University, Milton Keynes, UK

Abstract

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.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 04 August 2024

Files

Share

How to cite

Statistics