[seqfan] missing sequence: Hamiltonian paths on square grid

Neil Sloane njasloane at gmail.com
Sat Feb 9 04:26:48 CET 2013


Dear Sequence Fans, We have many sequences related to
the enumeration of Hamiltonian cycles on square grids.

The classic version is A003763, the number of Hamiltonian cycles
on a 2n X 2n grid, where quite a lot of terms are known.
But A003763 counts rotations and reflections as different.
Sol Golomb recently asked me for the number of inequivalent Hamiltonian
cycles if one says that two cycles are equivalent if they
differ only by a reflection and/or rotation.
For n = 1,2,3,..., A003763 begins 1, 6, 1072, 4638576, ...
and I just added a drawing to A003763 illustrating A003763(2) = 6.

The number of *inequivalent* Hamiltonian cycles begins a(1)=1, a(2)=2,
but I don't even know the next term. The attached drawing shows a few
Ham. cycles on the 6 X 6 grid. Since 1072/8 = 134, a(3) will be bigger than
134.
Oh, I forgot that I can't attach a jpeg file here.
I'll be happy to send it to anyone who wants to see it.

Neil

PS By the way, the two links in A003763 by Karavaev and Tittman look like
they may contain sequences that aren't yet in the OEIS - could someone
check?


More information about the SeqFan mailing list