Metraipolis › archive › dc_d479cd87a984
Hull Games of Induced Path Convexities in Graphs — arXiv:2609.30302
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.30302
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T02:59:20.183Z
- SHA-256 of the archived text
0fb4031c2b8340d9f478559e3dad10e0b1ff913736acb406f1ee4b000aea4f4d- Stable URL of this page
https://metraipolis.com/documento/dc_d479cd87a984
How to cite
Hull Games of Induced Path Convexities in Graphs — arXiv:2609.30302 — arXiv (en), https://arxiv.org/abs/2609.30302 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d479cd87a984 (Metraipolis archive dc_d479cd87a984, sha256 0fb4031c2b8340d9f478559e3dad10e0b1ff913736acb406f1ee4b000aea4f4d)
BibTeX
@misc{dcd479cd87a984,
title = {Hull Games of Induced Path Convexities in Graphs — arXiv:2609.30302},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.30302},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d479cd87a984; sha256 0fb4031c2b8340d9f478559e3dad10e0b1ff913736acb406f1ee4b000aea4f4d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.30302. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\mathrm{m}$-convexity and the $\ell_k$-convexities, based on induced paths and on induced paths of size at most $k$. We prove that the hull games $\mathrm{CHG}_{\mathrm{m}}$, $\mathrm{CHG}_{\ell_k}$ and their misère variants are PSPACE-complete for every $k\ge2$ 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 $\mathrm{CHG}_{\mathrm{m}}$ and $\mathrm{CHG}_{\ell_k}$ for any $k\ge2$ in disjoint unions of paths and cycles. For $k\ge3$ odd, we prove that Alice (1st player) wins $\mathrm{CHG}_{\ell_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=\alpha\cdot (k+1)-1$ with $\alpha\ge2$. For $k\ge2$ even, the only periodic nimber sequences of $\mathrm{CHG}_{\ell_k}$ obtained through extensive computational testing occurred for $k=2^h-4$ with $h\ge3$, e.g, $k\in\{4,12,28,60,\ldots\}$. In this case ($k=2^h-4$ with $h\ge3$), we prove that the nimber sequences of $\mathrm{CHG}_{\ell_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\in\{2k+1,5k+3\}$). Finally, we show that, for $k=2$, the game $\mathrm{CHG}_{\ell_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 $50$ million.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.CO).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.30302 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T02:28:17.937Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).