¿Cuántos caminos hamiltonianos hay en un gráfico casi regular?

Question

Que sea $G=(V,E)$ , donde $V=\{1,\ldots,n\}$ y $E=\{\{i,j\}\subset V;|i-j|\leq k\}$ y $k<n$ .
Para qué valores de $k\geq 2$ ¿podemos contar explícitamente el número de trayectorias hamiltonianas en $G$ ?

Answer 1

Valores explícitos para $k\leq 9$ y pequeños $n$ se indican en la OEIS:

k=2: http://oeis.org/A003274 (contiene algunas referencias y una función generadora)

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

Answer 2

S. Kitaev define los esquemas Path $P(n,M)$ como grafos con conjunto de vértices $\{1,2,\dots,n\}$ y bordes $(i,j)$ si $|i-j|\in M$ . Los grafos hamiltonianos en los esquemas de trayectorias fueron mencionados en "On uniquely k-determined permutations" por S. Avgustinovich y S. Kitaev. La fórmula no es sencilla ni siquiera en el caso de que $M=\{1,2\}$ ( aquí ), pero supongo que depende del tipo de fórmula que se busque.