Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.11282 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912329733505024 |
|---|---|
| author | Beluhov, Nikolai |
| author_facet | Beluhov, Nikolai |
| contents | Let $P$ be a connected bounded region in the plane formed out of $2 \times 2$ blocks joined by their sides. Peng and Rascoussier conjectured that all minimum-turn Hamiltonian cycles of $P$ exhibit a certain regular structure. We prove this conjecture in the special case when $P$ is a topological disk. The proof proceeds in two phases - a "downward" phase where we break apart an irregular Hamiltonian cycle into a collection of shorter cycles; and an "upward" phase where we put it back together in a different way so that, overall, the number of turns in it decreases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_11282 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimum-Turn Tours of Even Polyominoes Beluhov, Nikolai Combinatorics 05C38, 05C45 Let $P$ be a connected bounded region in the plane formed out of $2 \times 2$ blocks joined by their sides. Peng and Rascoussier conjectured that all minimum-turn Hamiltonian cycles of $P$ exhibit a certain regular structure. We prove this conjecture in the special case when $P$ is a topological disk. The proof proceeds in two phases - a "downward" phase where we break apart an irregular Hamiltonian cycle into a collection of shorter cycles; and an "upward" phase where we put it back together in a different way so that, overall, the number of turns in it decreases. |
| title | Minimum-Turn Tours of Even Polyominoes |
| topic | Combinatorics 05C38, 05C45 |
| url | https://arxiv.org/abs/2504.11282 |