How many Hamiltonians Paths there are in almost regular graph ? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T06:08:38Z http://mathoverflow.net/feeds/question/28649 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph How many Hamiltonians Paths there are in almost regular graph ? Leandro 2010-06-18T18:10:06Z 2011-04-20T21:19:01Z <p>Let be $G=(V,E)$, where <code>$V=\{1,\ldots,n\}$</code> and <code>$E=\{\{i,j\}\subset V;|i-j|\leq k\}$</code> and <code>$k&lt;n$</code>.<br> For which values of $k\geq 2$, can we count explicitly the number of Hamiltonian paths in $G$ ? </p> http://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph/28654#28654 Answer by Gjergji Zaimi for How many Hamiltonians Paths there are in almost regular graph ? Gjergji Zaimi 2010-06-18T19:00:35Z 2010-06-18T19:00:35Z <p>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\}$ (<a href="http://www.research.att.com/~njas/sequences/A069241" rel="nofollow">here</a>), but I guess it depends on what kind of formula you are looking for.</p> http://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph/29857#29857 Answer by Max Alekseyev for How many Hamiltonians Paths there are in almost regular graph ? Max Alekseyev 2010-06-29T01:54:56Z 2011-04-20T21:19:01Z <p>Explicit values for $k\leq 9$ and small $n$ are given in the OEIS:</p> <p>k=2: <a href="http://oeis.org/A003274" rel="nofollow">http://oeis.org/A003274</a> (contains some references and a generating function)</p> <p>k=3: <a href="http://oeis.org/A174700" rel="nofollow">http://oeis.org/A174700</a></p> <p>k=4: <a href="http://oeis.org/A174701" rel="nofollow">http://oeis.org/A174701</a></p> <p>k=5: <a href="http://oeis.org/A174702" rel="nofollow">http://oeis.org/A174702</a></p> <p>k=6: <a href="http://oeis.org/A177278" rel="nofollow">http://oeis.org/A177278</a></p> <p>k=7: <a href="http://oeis.org/A177279" rel="nofollow">http://oeis.org/A177279</a></p> <p>k=8: <a href="http://oeis.org/A177280" rel="nofollow">http://oeis.org/A177280</a></p> <p>k=9: <a href="http://oeis.org/A177281" rel="nofollow">http://oeis.org/A177281</a></p>