Node-Kayles on Trees
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909978721255424 |
|---|---|
| author | Songsuwan, Nuttanon |
| author_facet | Songsuwan, Nuttanon |
| contents | Node-Kayles is a well-known impartial combinatorial game played on graphs, where players alternately select a vertex and remove it along with its neighbors. By the Sprague-Grundy theorem, every position of an impartial game corresponds to a non-negative integer called its Grundy value. In this paper, we investigate the Grundy value sequences of $n$-regular trees as well as graphs formed by joining two $n$-regular trees with a path of length $k$. We derive explicit formulas and recursive relations for the associated Grundy value sequences. Furthermore, we prove that these sequences are eventually periodic and determine both their preperiod lengths and their periods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24221 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Node-Kayles on Trees Songsuwan, Nuttanon Combinatorics 05C57, 91A05, 91A46 Node-Kayles is a well-known impartial combinatorial game played on graphs, where players alternately select a vertex and remove it along with its neighbors. By the Sprague-Grundy theorem, every position of an impartial game corresponds to a non-negative integer called its Grundy value. In this paper, we investigate the Grundy value sequences of $n$-regular trees as well as graphs formed by joining two $n$-regular trees with a path of length $k$. We derive explicit formulas and recursive relations for the associated Grundy value sequences. Furthermore, we prove that these sequences are eventually periodic and determine both their preperiod lengths and their periods. |
| title | Node-Kayles on Trees |
| topic | Combinatorics 05C57, 91A05, 91A46 |
| url | https://arxiv.org/abs/2512.24221 |