5
$\begingroup$

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$ ?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Hi Gjergji, thank you very much for the reply. The special case $M={1,2}$ is the most important for me right now. $\endgroup$
    – Leandro
    Jun 18, 2010 at 22:02
6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Hi Max, thank you for the information. $\endgroup$
    – Leandro
    Jun 29, 2010 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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