Partizan Graph Convexity Games

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

The first paper of convexity on general graphs, in English, is the paper ``Convexity in graphs'', published in 1981. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which are impartial games and were investigated in a sequence of five papers until 2003.
Only in 2023 the first PSPACE-hardness result on impartial convexity games were proved.
In this paper, we introduce the partizan variants of these impartial games on the geodesic convexity and extend them to other graph convexities, obtaining winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from Conway's combinatorial game theory on partizan games. We also prove that the normal play and the misère play of the partizan hull game on the geodesic convexitiy is PSPACE-complete even in graphs with diameter two.

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 IFCE
  • 2 DC, UFC
  • 3 IC, UFAM
Track
  • 19. TAG – Graph Theory and Algorithms
Keywords
Convexity of graphs
Combinatorial games
PSPACE-Completeness
Graph classes