Winning Strategies for Impartial Convexity Games in Graphs

Vol 56, 2024 - 309208
Complete Articles (CA)
Favorite this paper
How to cite this paper?
Abstract

In 1981, the first paper in English on graph convexity was published. Three years later, in 1984, one of its authors, Frank Harary, introduced the first convexity games. Although defined 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 were able to use the Sprague-Grundy theory to solve convexity games in special graphs, such as trees. In addition, we have proven that one of these games is PSPACE-hard, which puts it a level of complexity above NP-hard problems.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 DC, UFC
Track
  • 19. TAG – Graph Theory and Algorithms
Keywords
Convexity in Graphs
Combinatorial Game Theory
Sprague-Grundy theory