A367123 - OEIS

%I #15 Nov 19 2023 11:36:14

%S 1,1,0,2,16800

%N Number of Hamiltonian cycles in the n-omino graph defined in A098891.

%C 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.

%C A cycle and its reverse are not both counted.

%C 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.

%H Pontus von Brömssen, <a href="/A367123/a367123.svg">A Hamiltonian cycle in the hexomino graph</a>. In this cycle, all intermediates are (connected) pentominoes.

%H <a href="/index/Pol#polyominoes">Index entries for sequences related to polyominoes</a>.

%F a(n) > 0 for 4 <= n <= 13.

%F a(n) >= A367436(n).

%e 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.

%e 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.

%e See links for an example for n = 6.

%Y Cf. A000105, A003216, A098891, A367124, A367125, A367126, A367127, A367436.

%K nonn,more

%O 1,4

%A _Pontus von Brömssen_, Nov 05 2023