A140519 - OEIS

%I #33 Mar 19 2020 20:10:03

%S 1,3,16,2830,2462064,22853860116,1622043117414624,

%T 961742089476282321684,4601667243759511495116347104,

%U 179517749570891592016479828267003018,56735527086758553613684823040730404215973136,145328824470156271670635015466987199469360063082789418

%N Number of (undirected) Hamiltonian cycles on the n X n king graph.

%C Or, number of Hamiltonian cycles in the graph P_n X P_n (strong product of two paths of length n-1).

%C If the direction of the tour is to be taken into account, the numbers for n > 1 must be multiplied by 2 (see A140521).

%C Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

%D D. E. Knuth, The Art of Computer Programming, Section 7.1.4, in preparation.

%H N. J. A. Sloane, <a href="/A140519/b140519.txt">Table of n, a(n) for n = 1..16</a> [From Pettersson 2014]

%H Ville H. Pettersson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p7">Enumerating Hamiltonian Cycles</a>, The Electronic Journal of Combinatorics, Volume 21, Issue 4, 2014.

%H Ville Pettersson, <a href="https://aaltodoc.aalto.fi/bitstream/handle/123456789/17688/isbn9789526063652.pdf?sequence=1">Graph Algorithms for Constructing and Enumerating Cycles and Related Structures</a>, Dissertation, Aalto, Finland, 2015.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KingGraph.html">King Graph</a>

%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs, Hamiltonian</a>

%Y Cf. A001230, A140521.

%K nonn,walk

%O 1,2

%A _Don Knuth_, Jul 26 2008

%E New name from _Eric W. Weisstein_, May 06 2019