Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

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
add comment

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
add comment

Your Answer

 
discard

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.