Winning strategies for convexity games on graphs
DOI:
https://doi.org/10.5753/reic.2024.4644Abstract
In 1981, the first paper on graph convexity was published. Three years later, in 1984, one of its authors, Frank Harary, introduced the first convexity games. Despite having been created a long time ago, the last research on convexity games dated back to 2003, with few significant results due to their difficulty. In this work, we use the Sprague-Grundy Theory to solve these games in special graphs, such as trees. Furthermore, we proved that one of these games is PSPACE-hard, which puts it one level of computational complexity above NP-hard problems.Downloads
References
Bouton, C. L. (1901). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3(1/4):35–39.
Buckley, F. and Harary, F. (1985a). Closed geodetic games for graphs. Congr Numerantium, 47:131–138. Proc 16th Southeastern Combinatorics, Graph Th and Comput.
Buckley, F. and Harary, F. (1985b). Geodetic games for graphs. Quaest Math, 8:321–334.
Grundy, P. M. (1939). Mathematics and games. Eureka, 2:6–8.
Harary, F. (1984). Convexity in graphs: Achievement and avoidance games. In Annals of Discrete Mathematics (20), volume 87, page 323. North-Holland.
Harary, F. and Nieminem, J. (1981). Convexity in graphs. J Differ Geom, 16(1):185–190.
Haynes, T., Henning, M., and Tiller, C. (2003). Geodetic achievement and avoidance games for graphs. Quaestiones Mathematicae, 26:389–397.
Hearn, R. and Demaine, E. (2009). Games, Puzzles and Computation. A. K. Peters Ltd.
Nečásková, M. (1988). A note on achievement geodetic game. Quaest Math, 12:115–119.
Schaefer, T. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2):185–225.
Sprague, R. (1936). Über mathematische Kampfspiele. Tôhoku Math J, 41:438–444.
Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. 5th Int. Congress of Mathematicians, pages 501–504.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Os autores
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
