Hull Games of Induced Path Convexities in Graphs
Abstract
In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic m-convexity and the ℓk-convexities, based on induced paths and on induced paths of size at most k. We prove that the hull games CHGm, CHGℓk and their misère variants are PSPACE-complete for every k≥2 even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games CHGm and CHGℓk for any k≥2 in disjoint unions of paths and cycles. For k≥3 odd, we prove that Alice (1st player) wins CHGℓk in the path Pn if and only if n is odd and she wins in the cycle Cn if and only if n=3 or n=α· (k+1)−1 with α≥2. For k≥2 even, the only periodic nimber sequences of CHGℓk obtained through extensive computational testing occurred for k=2h−4 with h≥3, e.g, k∈{4,12,28,60,…}. In this case (k=2h−4 with h≥3), we prove that the nimber sequences of CHGℓk in Pn and in Cn are periodic and Alice loses (resp. wins) in Pn (resp. Cn) with n>k only when n=3k+4 (resp. n∈{2k+1,5k+3}). Finally, we show that, for k=2, the game CHGℓ2 in paths Pn is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of n up to $150$ million.
Related
- Coloring graphs with no long induced path
- Undirected edge geography games on stacked prism graphs
- Connected Coloring Games on Corona Products of Graphs
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Optimal path decompositions of sparse random graphs
BibTeX
@misc{costa2026hull,
title = {{Hull Games of Induced Path Convexities in Graphs}},
author = {Eurinardo Costa and Leon Almeida and Rudini Sampaio},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.30302},
eprint = {2609.30302},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30302},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hull Games of Induced Path Convexities in Graphs
AU - Eurinardo Costa
AU - Leon Almeida
AU - Rudini Sampaio
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2609.30302
UR - https://arxiv.org/abs/2609.30302
AB - In 1984, Frank Harary introduced the first convexity games in graphs, all of them based on the geodesic convexity, which is the graph convexity related to shortest paths. In 2024, Araújo et al. obtained the first PSPACE-hardness proofs on some of these geodesic games and generalized them to any graph convexity. In this paper, we investigate convexity games on several known induced path convexities: the monophonic m-convexity and the ℓ_k-convexities, based on induced paths and on induced paths of size at most k. We prove that the hull games CHG_m, CHG_ℓ_k and their misère variants are PSPACE-complete for every k≥2 even in graphs with diameter at most 3. We also use the Sprague-Grundy Theory to obtain a polynomial time algorithm to decide the winner of the games CHG_m and CHG_ℓ_k for any k≥2 in disjoint unions of paths and cycles. For k≥3 odd, we prove that Alice (1st player) wins CHG_ℓ_k in the path P_n if and only if n is odd and she wins in the cycle C_n if and only if n=3 or n=α· (k+1)−1 with α≥2. For k≥2 even, the only periodic nimber sequences of CHG_ℓ_k obtained through extensive computational testing occurred for k=2^h−4 with h≥3, e.g, k∈{4,12,28,60,…}. In this case (k=2^h−4 with h≥3), we prove that the nimber sequences of CHG_ℓ_k in P_n and in C_n are periodic and Alice loses (resp. wins) in P_n (resp. C_n) with n>k only when n=3k+4 (resp. n∈{2k+1,5k+3}). Finally, we show that, for k=2, the game CHG_ℓ_2 in paths P_n is closely related to the classical game \emph{Couples-are-Forever} of J. H. Conway: it is still an open problem if the nimber sequence is periodic or not and Alice loses only for 12 values of n up to $150$ million.
ER -