OFFSET
1,4
COMMENTS
The n-omino graph has all A000105(n) free n-ominoes as nodes, and two n-ominoes are joined by an edge if one can be obtained from the other by moving one cell. The intermediate is allowed not to be a connected (n-1)-omino; for example, there is an edge between the V and W pentominoes, but to transform one to the other the central cell must be moved, and the remaining 4 cells is not a tetromino.
A cycle and its reverse are not both counted.
We follow the convention in A003216 that the complete graphs on 1 and 2 nodes have 1 and 0 Hamiltonian cycles, respectively, so that a(1) = a(2) = 1 and a(3) = 0, but it could also be argued that a(1) = a(2) = 0 and/or a(3) = 1.
LINKS
Pontus von Brömssen, A Hamiltonian cycle in the hexomino graph. In this cycle, all intermediates are (connected) pentominoes.
FORMULA
a(n) > 0 for 4 <= n <= 13.
a(n) >= A367436(n).
EXAMPLE
For n = 4, there are a(4) = 2 Hamiltonian cycles in the tetromino graph: I-L-O-S-T-I and I-L-S-O-T-I, using conventional names of the tetrominoes.
For n = 5, one of the a(5) = 16800 Hamiltonian cycles in the pentomino graph is I-L-P-U-V-T-N-W-Z-F-X-Y-I.
See links for an example for n = 6.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Pontus von Brömssen, Nov 05 2023
STATUS
approved