The Closed Geodetic Game: algorithms and strategies
Abstract
The geodetic closure of a set S of vertices of a graph is the set of all vertices in shortest paths between pairs of vertices of S. A set S of vertices in a graph is geodetic if its geodetic closure contains all the vertices of the graph. Several authors have studied variants of games around constructing geodetic sets. The most studied of those, Geodetic Game, was introduced by Harary in 1984 and developed by Buckley and Harary in 1985. It is an achievement game: both players construct together a geodetic set by alternately adding vertices to the set, the winner being the one who plays last. However, this version of the game allows the players to select vertices that already are in the geodetic closure of the current set. We study the more natural variant, called Closed Geodetic Game, where the players alternate adding to S vertices that are not in the geodetic closure of S. This variant was also introduced in another, less-noticed, paper by Buckley and Harary in 1985, and only studied since then in the context of trees by Araujo et al. in 2024. We provide a full characterization of the Sprague-Grundy values (equivalence values for games) of graph classes such as paths and cycles, of the outcomes of the Cartesian product of several graphs in function of their individual outcomes, and give polynomial-time algorithms to determine the Sprague-Grundy values in cactus and block graphs.
Related
- On Large Covers and the Strong Closed Discrete Game
- Solution and Optimal Strategies for a Differential Game of Pursuit-Evasion with Point-Wise Constraints
- Information Disclosure Strategies of Live-Streaming E-Commerce Supply Chains in the AI Era: A Game-Theoretic Analysis
- Optimistic Gradient Algorithms with Randomized Coordinate and Variance Reduction Strategies for Composite Inclusions
- Cost-effectiveness of end-game strategies against sleeping sickness across the Democratic Republic of Congo
BibTeX
@article{dailly2026closed,
title = {{The Closed Geodetic Game: algorithms and strategies}},
author = {Antoine Dailly and Harmender Gahlawat and Zin Mar Myint},
journal = {Theoretical Computer Science},
year = {2026},
month = oct,
doi = {10.1016/j.tcs.2026.116186},
eprint = {2409.20505},
archivePrefix = {arXiv},
url = {https://hal.inrae.fr/hal-04715333v3},
note = {CC BY-SA 4.0},
}
RIS
TY - JOUR
TI - The Closed Geodetic Game: algorithms and strategies
AU - Antoine Dailly
AU - Harmender Gahlawat
AU - Zin Mar Myint
PY - 2026
DA - 2026/10/15
JO - Theoretical Computer Science
DO - 10.1016/j.tcs.2026.116186
UR - https://hal.inrae.fr/hal-04715333v3
AB - The geodetic closure of a set S of vertices of a graph is the set of all vertices in shortest paths between pairs of vertices of S. A set S of vertices in a graph is geodetic if its geodetic closure contains all the vertices of the graph. Several authors have studied variants of games around constructing geodetic sets. The most studied of those, Geodetic Game, was introduced by Harary in 1984 and developed by Buckley and Harary in 1985. It is an achievement game: both players construct together a geodetic set by alternately adding vertices to the set, the winner being the one who plays last. However, this version of the game allows the players to select vertices that already are in the geodetic closure of the current set. We study the more natural variant, called Closed Geodetic Game, where the players alternate adding to S vertices that are not in the geodetic closure of S. This variant was also introduced in another, less-noticed, paper by Buckley and Harary in 1985, and only studied since then in the context of trees by Araujo et al. in 2024. We provide a full characterization of the Sprague-Grundy values (equivalence values for games) of graph classes such as paths and cycles, of the outcomes of the Cartesian product of several graphs in function of their individual outcomes, and give polynomial-time algorithms to determine the Sprague-Grundy values in cactus and block graphs.
SN - 0304-3975
SN - 1879-2294
ER -