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
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
EXAMPLE
There are six Hamiltonian cycles in the cube, but they are isomorphic so a(3) = 1.
CROSSREFS
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