← 研踪 PaperTrailarXiv:2609.30302 · v4
Hull Games of Induced Path Convexities in Graphs
首次提交 2026-09-22 05:52
版本更新 2026-10-27 12:24
雷达观测 2026-10-29 00:35
摘要
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=α\cdot (k+1)-1$ with $α\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 $150$ million.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v4 · 2026-10-27 12:24 · 最新观测版本
Hull Games of Induced Path Convexities in Graphs
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=α\cdot (k+1)-1$ with $α\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 $150$ million.
查看此版本解读 →查看此版本原文 ↗