The Closed Geodetic Game: algorithms and strategies - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement
Pré-Publication, Document De Travail Année : 2024

The Closed Geodetic Game: algorithms and strategies

Résumé

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 several products of graphs in function of the outcomes of the two graphs, and give polynomial-time algorithms to determine the Sprague-Grundy values in cactus and block graphs.
Fichier principal
Vignette du fichier
prepub.pdf (558.74 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04715333 , version 1 (30-09-2024)

Identifiants

  • HAL Id : hal-04715333 , version 1

Citer

Antoine Dailly, Harmender Gahlawat, Zin Mar Myint. The Closed Geodetic Game: algorithms and strategies. 2024. ⟨hal-04715333⟩
22 Consultations
6 Téléchargements

Partager

More