MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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: (contains some references and a generating function)








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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.