|
%I #100 Nov 16 2022 15:26:20
%S 1,1,1,9,237675,777739016577752714
%N Number of Hamiltonian cycles in the n-hypercube up to automorphism.
%C Here we count equivalence classes under the full automorphism group of the n-cube. - _N. J. A. Sloane_, Sep 06 2012
%C a(4) is due to Gilbert and a(5) is due to Dejter & Delgado.
%C Comments on Abbott's (1966) lower bound, from _Charles R Greathouse IV_ and _David Applegate_ (Sequence Fans Mailing List, Dec 06 2012: (Start)
%C 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)].
%C 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.
%C Looking at Abbot's paper, at least one error is the claim "it is easy to verify that (12) implies (3)."
%C (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)
%H H. L. Abbott, <a href="https://doi.org/10.4153/CMB-1966-068-6">Hamiltonian circuits and paths on the n-cube</a>, Canad. Math. Bull., 9 (1966), pp. 557-562.
%H Yury Chebiryak and Daniel Kroening, <a href="ftp://ftp.inf.ethz.ch/doc/tech-reports/6xx/601.pdf">Towards a classification of Hamiltonian cycles in the 6-cube</a>, Journal on Satisfiability, Boolean Modeling and Computation 4 (2008) pp. 57-74.
%H I. J. Dejter and A. A. Delgado, <a href="https://www.researchgate.net/publication/250340326_Classes_of_Hamilton_Cycles_in_the_5Cube">Classes of Hamiltonian cycles in the 5-cube</a>, J. Combinat. Math, Combinat. Comput, 61 (2007), pp. 81-95.
%H R. J. Douglas, <a href="http://dx.doi.org/10.1016/0012-365X(77)90143-1">Bounds on the number of Hamiltonian circuits in the n-cube</a>, Discrete Mathematics, 17 (1977), 143-146.
%H E. N. Gilbert, <a href="https://archive.org/details/bstj37-3-815">Gray codes and paths on the n-cube</a>, Bell Syst. Tech. J. 37 (1958), pp. 815-826.
%H Harri Haanpaa and Patric R. J. Östergård, <a href="https://doi.org/10.1090/S0025-5718-2013-02741-X">Counting Hamiltonian cycles in bipartite graphs</a>, Math. Comp., 83 (2014), 979-995.
%H Frank Ruskey, <a href="https://page.math.tu-berlin.de/~felsner/SemWS17-18/Ruskey-Comb-Gen.pdf">Combinatorial Generation</a> (2003), see ch. 6.7.
%H D. H. Smith, <a href="http://dx.doi.org/10.4153/CMB-1974-137-9">Hamiltonian circuits on the n-cube</a>, Canadian Mathematical Bulletin 17 (1975), pp. 759-761.
%F a(n) < n^(2^n).
%F 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!]
%e There are six Hamiltonian cycles in the cube, but they are isomorphic so a(3) = 1.
%Y Cf. A003042, A006069, A066037, A091302.
%K nonn,hard,more,nice
%O 1,4
%A _Charles R Greathouse IV_, Jan 25 2012
%E a(6) from Haanpaa & Ostergard 2012. - _N. J. A. Sloane_, Sep 06 2012
%E Edited by _N. J. A. Sloane_, Dec 16 2012
| 