|
%I #36 Mar 12 2023 08:53:02
%S 1,144,4960608,55493434415544000
%N Number of (directed) Hamiltonian paths on the n X n X n grid graph.
%C A general purpose matrix-transfer method can be used to compute values up to a(4). Using a diagonal sweep from one corner to the opposite corner will help to reduce the number of states. - _Andrew Howroyd_, Dec 20 2015
%C Schram & Schiessel (see Links) quote a different result for a(4): 27747833510015886 undirected Hamiltonian walks, which would double to 55495667020031772 directed Hamiltonian walks. However, that number is not divisible by 8 and thus cannot be correct. - _Arun Giridhar_, Dec 15 2015
%H Raoul D. Schram and Helmut Schiessel, <a href="http://dx.doi.org/10.1088/1751-8113/46/48/485001">Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding</a>, Journal of Physics A: Mathematical and Theoretical, vol 46 (2013), 485001.
%H Raoul D. Schram and Helmut Schiessel, <a href="http://dx.doi.org/10.1088/1751-8113/49/36/369501">Corrigendum: Exact enumeration of Hamiltonian walks on the 4x4x4 cube and applications to protein folding</a>, Journal of Physics A: Mathematical and Theoretical, vol 49 (2016), 369501.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianPath.html">Hamiltonian Path</a>
%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>
%e For n = 1, there is a trivial Hamiltonian path of length 0.
%e For n = 2, the 144 paths fall in three different equivalence classes. Two of the three classes can be derived by taking a Hamiltonian cycle on a cube and deleting a single edge. The third class is a spiral path that ends at the opposite corner from its starting point.
%Y Cf. A003763, A096969.
%K nonn,hard,more,bref
%O 1,2
%A _Eric W. Weisstein_, Jul 23 2011
%E a(4) from _Andrew Howroyd_, Nov 15 2015
%E a(1) corrected by _Arun Giridhar_, Dec 20 2015
| 