A381474 -id:A381474 - cp's OEIS frontend

A381730 Number of minimum connected dominating sets in the n X n grid graph.

1, 4, 2, 16, 126, 24, 800, 16288, 16, 87216, 3554000, 16, 13400336, 882342944, 16, 2376303680

Offset: 1

Eric W. Weisstein, Mar 05 2025

			From _Andrew Howroyd_, Mar 19 2025: (Start)
One of 16 arrangements for a(9):
  . X . . . . . . .
  . X X X X X X X X
  . X . . X . . X .
  . X . . X . . X .
  . X . . X . . X .
  . X . . X . . X .
  . X . . X . . X .
  . X . . X . . X .
  . X . . X . . X .
(End)

Eric Weisstein's World of Mathematics, Connected Dominating Set.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 1 to 6 plus 9, 12, 15, 18
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 7

Main diagonal of A381474.
Cf. A287690, A347632.
Cf. A369692 (connected domination numbers).

a(3*n) = 16 for n >= 3. - Andrew Howroyd, Mar 19 2025

a(6)-a(16) from Andrew Howroyd, Mar 19 2025

A381475 Array read by antidiagonals: T(m,n) is the connected domination number of the grid graph P_m X P_n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 3, 4, 3, 4, 3, 4, 5, 4, 4, 5, 4, 5, 6, 5, 7, 5, 6, 5, 6, 7, 6, 9, 9, 6, 7, 6, 7, 8, 7, 10, 11, 10, 7, 8, 7, 8, 9, 8, 12, 12, 12, 12, 8, 9, 8, 9, 10, 9, 14, 15, 14, 15, 14, 9, 10, 9, 10, 11, 10, 15, 17, 16, 16, 17, 15, 10, 11, 10

Offset: 1

Andrew Howroyd, Mar 19 2025

			Table begins:
=========================================================
m\n |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
----+----------------------------------------------------
  1 |  1  1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 ...
  2 |  1  2  2  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
  3 |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
  4 |  2  4  4  7  9 10 12 14 15 17 19 20 22 24 25 27 ...
  5 |  3  5  5  9 11 12 15 17 18 21 23 24 27 29 30 33 ...
  6 |  4  6  6 10 12 14 16 18 20 22 24 26 28 30 32 34 ...
  7 |  5  7  7 12 15 16 20 23 24 28 31 32 36 39 40 44 ...
  8 |  6  8  8 14 17 18 23 26 27 32 35 36 41 44 45 50 ...
  9 |  7  9  9 15 18 20 24 27 30 33 36 39 42 45 48 51 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Main diagonal is A369692.

Cf. A300358, A350823, A381474.

T(m,n) = T(n,m).

cp's OEIS Frontend

A381730 Number of minimum connected dominating sets in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions