A367125 -id:A367125 - cp's OEIS frontend

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

1, 1, 0, 2, 16800

Offset: 1

Pontus von Brömssen, Nov 05 2023

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.

			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.

Pontus von Brömssen, A Hamiltonian cycle in the hexomino graph. In this cycle, all intermediates are (connected) pentominoes.
Index entries for sequences related to polyominoes.

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

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

a(n) >= A367436(n).

A367124 Maximum degree of the n-omino graph defined in A098891.

Original entry on oeis.org

0, 0, 1, 4, 10, 28, 39, 68, 81, 116, 140, 186, 204

Offset: 1

Pontus von Brömssen, Nov 05 2023

Largest number of free polyominoes that can be made from a polyomino with n cells by moving one of its cells (not counting itself).

			For 1 <= n <= 12, the following polyominoes have the maximum degree in the polyomino graph of their respective sizes (see also link):
                                                _             _
             _           _        _    _      _| |     _     | |
        _   | |   _     | |     _| |  | |_   |_  |   _| |    | |_
   _   | |  | |  | |_   | |_   |_  |  |   |    | |  |_  |_   |   |
  |_|  |_|  |_|  |_ _|  |_ _|    |_|  |_ _|    |_|    |_ _|  |_ _|
                     _          _      _        _
     _      _       | |       _| |    | |      | |_      _ _
   _| |    | |      | |      |_  |_   | |_ _   |   |_   |   |_ _
  |_  |_   | |_ _   | |_ _     |   |  |  _  |  |  _  |  |  _ _  |
    |   |  |     |  |     |    |   |  | |_| |  | |_| |  | |_ _| |
    |_ _|  |_ _ _|  |_ _ _|    |_ _|  |_ _ _|  |_ _ _|  |_ _ _ _|

Pontus von Brömssen, Polyominoes of maximum degree for 1 <= n <= 13.
Index entries for sequences related to polyominoes.

Cf. A098891, A367123, A367125, A367437.

Row maxima of A367126.

a(n) >= A367437(n).

A367126 a(n) is the degree of the polyomino with binary code A246521(n+1) in the n-omino graph defined in A098891.

Original entry on oeis.org

0, 0, 1, 1, 4, 3, 4, 3, 2, 10, 9, 5, 9, 10, 9, 8, 9, 10, 9, 4, 2, 16, 28, 16, 14, 12, 12, 18, 15, 20, 21, 16, 16, 16, 15, 18, 20, 11, 14, 13, 18, 6, 12, 16, 18, 11, 9, 11, 15, 22, 20, 11, 19, 14, 16, 3, 38, 36, 35, 33, 31, 32, 38, 25, 31, 38, 17, 14, 30, 14, 26

Offset: 1

Pontus von Brömssen, Nov 05 2023

Number of free polyominoes that can be made from the polyomino with binary code A246521(n+1) by moving one of its cells (not counting itself).

Can be read as an irregular triangle, whose m-th row contains A000105(m) terms, m >= 1.

			As an irregular triangle:
   0;
   0;
   1, 1;
   4, 3, 4, 3,  2;
  10, 9, 5, 9, 10, 9, 8, 9, 10, 9, 4, 2;
  ...
For n = 8, A246521(8+1) = 30 is the binary code of the S-tetromino. By moving one cell of the S-tetromino, we can obtain the L, O, and T tetrominoes (but not the I tetromino), so a(8) = 3.

Pontus von Brömssen, Table of n, a(n) for n = 1..6473 (rows 1..10).
Index entries for sequences related to polyominoes.

Cf. A000105, A098891, A246521, A367123, A367124 (row maxima), A367125, A367439, A367443.

a(n) >= A367439(n).

A367438 Number of polyominoes with n cells that have the maximum degree (A367437(n)) in the polyomino graph PG(n) defined in A367435.

Original entry on oeis.org

1, 1, 2, 2, 3, 1, 1, 1, 4, 2, 2, 1, 9

Offset: 1

Pontus von Brömssen, Nov 18 2023

Pontus von Brömssen, Polyominoes of maximum degree for 1 <= n <= 13.
Index entries for sequences related to polyominoes.

Cf. A367125, A367435, A367437.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367124 Maximum degree of the n-omino graph defined in A098891.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367126 a(n) is the degree of the polyomino with binary code A246521(n+1) in the n-omino graph defined in A098891.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367438 Number of polyominoes with n cells that have the maximum degree (A367437(n)) in the polyomino graph PG(n) defined in A367435.

Views

Author

Keywords

Links

Crossrefs