Take the 2-minute tour ×

Let be $G=(V,E)$, where $V=\{1,\ldots,n\}$ and $E=\{\{i,j\}\subset V;|i-j|\leq k\}$ and $k<n$.
For which values of $k\geq 2$, can we count explicitly the number of Hamiltonian paths in $G$ ?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

S. Kitaev defines Path schemes $P(n,M)$ as graphs with vertex set $\{1,2,\dots,n\}$ and edges $(i,j)$ iff $|i-j|\in M$. Hamiltonian graphs on path schemes were mentioned in "On uniquely k-determined permutations" by S. Avgustinovich and S. Kitaev. The formula is not simple even in the case where $M=\{1,2\}$ (here), but I guess it depends on what kind of formula you are looking for.

share|improve this answer
Hi Gjergji, thank you very much for the reply. The special case $M={1,2}$ is the most important for me right now. –  Leandro Jun 18 '10 at 22:02

Explicit values for $k\leq 9$ and small $n$ are given in the OEIS:

k=2: http://oeis.org/A003274 (contains some references and a generating function)

k=3: http://oeis.org/A174700

k=4: http://oeis.org/A174701

k=5: http://oeis.org/A174702

k=6: http://oeis.org/A177278

k=7: http://oeis.org/A177279

k=8: http://oeis.org/A177280

k=9: http://oeis.org/A177281

share|improve this answer
Hi Max, thank you for the information. –  Leandro Jun 29 '10 at 9:32

Your Answer


