A159344 Number of Hamiltonian cycles in the n-hypercube up to automorphism.

1, 1, 1, 9, 237675, 777739016577752714

Offset

1,4

Comments

Here we count equivalence classes under the full automorphism group of the n-cube. - N. J. A. Sloane, Sep 06 2012

a(4) is due to Gilbert and a(5) is due to Dejter & Delgado.

Comments on Abbott's (1966) lower bound, from Charles R Greathouse IV and David Applegate (Sequence Fans Mailing List, Dec 06 2012: (Start)

a(n) is, in Abbott's terminology, h*(n); see (2) and (3) which yield a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n) [Note that we have written sqrt(294) for 7 sqrt(6)].

Unfortunately, the lower bound seems incompatible with the known values of a(n), even for a(3) and a(4) which were known to Abbott.

Looking at Abbot's paper, at least one error is the claim "it is easy to verify that (12) implies (3)."

(12) is h(m+3) >= 6^2^m h(m), which implies h(m) >= 6^2^(m-3) for m >= 4, or h(m) >= 2/5 * (6^2^(m-3)) for m >= 1, but certainly doesn't imply (3) h(m) >= (7 sqrt(6))^(2^n-4). (End)

Links

Table of n, a(n) for n=1..6.

H. L. Abbott, Hamiltonian circuits and paths on the n-cube, Canad. Math. Bull., 9 (1966), pp. 557-562.

Yury Chebiryak and Daniel Kroening, Towards a classification of Hamiltonian cycles in the 6-cube, Journal on Satisfiability, Boolean Modeling and Computation 4 (2008) pp. 57-74.

I. J. Dejter and A. A. Delgado, Classes of Hamiltonian cycles in the 5-cube, J. Combinat. Math, Combinat. Comput, 61 (2007), pp. 81-95.

R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.

E. N. Gilbert, Gray codes and paths on the n-cube, Bell Syst. Tech. J. 37 (1958), pp. 815-826.

Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp., 83 (2014), 979-995.

Frank Ruskey, Combinatorial Generation (2003), see ch. 6.7.

D. H. Smith, Hamiltonian circuits on the n-cube, Canadian Mathematical Bulletin 17 (1975), pp. 759-761.

Formula

a(n) < n^(2^n).

a(n) >= sqrt(294)^(2^n-4)/(n! * 2^n) and a(n) >= A066037(n)/A000165(n) due to Abbott 1966. [Warning: see Comments above!]

Example

There are six Hamiltonian cycles in the cube, but they are isomorphic so a(3) = 1.

Crossrefs

Cf. A003042, A006069, A066037, A091302.

Sequence in context: A109464 A300195 A368068 * A120352 A225069 A058468

Adjacent sequences: A159341 A159342 A159343 * A159345 A159346 A159347

Keyword

nonn,hard,more,nice

Author

Charles R Greathouse IV, Jan 25 2012

Extensions

a(6) from Haanpaa & Ostergard 2012. - N. J. A. Sloane, Sep 06 2012

Edited by N. J. A. Sloane, Dec 16 2012

Status

approved