A conjecture on the Crazy Knight's Tour Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918480641523712 |
|---|---|
| author | Mella, Lorenzo Pasotti, Anita |
| author_facet | Mella, Lorenzo Pasotti, Anita |
| contents | Let $A$ be an $m\times n$ toroidal array containing filled and empty cells. Fix an orientation $R=(r_1,\dots,r_m)$ of each row and an orientation $C=(c_1,\dots,c_n)$ of each column of $A$. Given an initial filled cell $(i_1,j_1)$ consider the list $ L_{R,C}=((i_1,j_1),(i_2,j_2),\ldots,(i_k,j_k),$ $(i_{k+1},j_{k+1}),\ldots)$ where $j_{k+1}$ is the column index of the filled cell $(i_k,j_{k+1})$ of the row $R_{i_k}$ next to $(i_k,j_k)$ in the orientation $r_{i_k}$, and where $i_{k+1}$ is the row index of the filled cell of the column $C_{j_{k+1}}$ next to $(i_k,j_{k+1})$ in the orientation $c_{j_{k+1}}$. The problem is the following.
Crazy Knight's Tour Problem: Do there exist $R$ and $C$ such that the list $L_{R,C}$ covers all the filled cells of $A$?
This problem was introduced by Costa, Dalai and Pasotti to construct new biembeddings of graphs on surfaces starting from an Heffter array. Here we provide solution to the Crazy Knight's Tour Problem for infinite classes of cyclically $k$-diagonal square arrays, namely square arrays whose filled cells are exactly those of $k$ consecutive diagonals. These new constructions together with some known results induce us to propose the following.
Conjecture: Let $A$ be a cyclically $k$-diagonal square array of order $n$. Then there exists a solution to the Crazy Knight's Tour Problem on $A$ if and only if $n$ and $k$ are odd integers with $n\geq k \geq3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_09054 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A conjecture on the Crazy Knight's Tour Problem Mella, Lorenzo Pasotti, Anita Combinatorics Let $A$ be an $m\times n$ toroidal array containing filled and empty cells. Fix an orientation $R=(r_1,\dots,r_m)$ of each row and an orientation $C=(c_1,\dots,c_n)$ of each column of $A$. Given an initial filled cell $(i_1,j_1)$ consider the list $ L_{R,C}=((i_1,j_1),(i_2,j_2),\ldots,(i_k,j_k),$ $(i_{k+1},j_{k+1}),\ldots)$ where $j_{k+1}$ is the column index of the filled cell $(i_k,j_{k+1})$ of the row $R_{i_k}$ next to $(i_k,j_k)$ in the orientation $r_{i_k}$, and where $i_{k+1}$ is the row index of the filled cell of the column $C_{j_{k+1}}$ next to $(i_k,j_{k+1})$ in the orientation $c_{j_{k+1}}$. The problem is the following. Crazy Knight's Tour Problem: Do there exist $R$ and $C$ such that the list $L_{R,C}$ covers all the filled cells of $A$? This problem was introduced by Costa, Dalai and Pasotti to construct new biembeddings of graphs on surfaces starting from an Heffter array. Here we provide solution to the Crazy Knight's Tour Problem for infinite classes of cyclically $k$-diagonal square arrays, namely square arrays whose filled cells are exactly those of $k$ consecutive diagonals. These new constructions together with some known results induce us to propose the following. Conjecture: Let $A$ be a cyclically $k$-diagonal square array of order $n$. Then there exists a solution to the Crazy Knight's Tour Problem on $A$ if and only if $n$ and $k$ are odd integers with $n\geq k \geq3$. |
| title | A conjecture on the Crazy Knight's Tour Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2311.09054 |