

A159344


Number of Hamiltonian cycles in the nhypercube up to automorphism.


4




OFFSET

1,4


COMMENTS

Here we count equivalence classes under the full automorphism group of the ncube.  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^n4)/(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^(m3) for m >= 4, or h(m) >= 2/5 * (6^2^(m3)) for m >= 1, but certainly doesn't imply (3) h(m) >= (7 sqrt(6))^(2^n4). (End)


LINKS

Table of n, a(n) for n=1..6.
H. L. Abbott, Hamiltonian circuits and paths on the ncube, Canad. Math. Bull., 9 (1966), pp. 557562.
Yury Chebiryak and Daniel Kroening, Towards a classification of Hamiltonian cycles in the 6cube, Journal on Satisfiability, Boolean Modeling and Computation 4 (2008) pp. 5774.
I. J. Dejter and A. A. Delgado, Classes of Hamiltonian cycles in the 5cube, J. Combinat. Math, Combinat. Comput, 61 (2007), pp. 8195.
R. J. Douglas, Bounds on the number of Hamiltonian circuits in the ncube, Discrete Mathematics, 17 (1977), 143146.
E. N. Gilbert, Gray codes and paths on the ncube, Bell Syst. Tech. J. 37 (1958), pp. 815826.
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp., 83 (2014), 979995.
Frank Ruskey, Combinatorial Generation (2003), see ch. 6.7.
D. H. Smith, Hamiltonian circuits on the ncube, Canadian Mathematical Bulletin 17 (1975), pp. 759761.


FORMULA

a(n) < n^(2^n).
a(n) >= sqrt(294)^(2^n4)/(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: A034995 A109464 A300195 * A120352 A225069 A058468
Adjacent sequences: A159341 A159342 A159343 * A159345 A159346 A159347


KEYWORD

nonn,hard,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



