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

1, 1, 1, 9, 237675, 777739016577752714

Offset: 1

Author

Charles R Greathouse IV, Jan 25 2012

Keywords

• nonn
• hard
• more
• nice

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)

Examples

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

Links

• 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.

Crossrefs

Cf. A003042, A006069, A066037, A091302.

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!]

Extensions

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

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