A369692 -id:A369692 - 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

A370428 Connected domination number of the n X n king graph.

Original entry on oeis.org

1, 1, 1, 4, 5, 8, 12, 15, 20, 24, 28, 33, 39, 46, 52, 58

Offset: 1

Alexander D. Healy, Feb 24 2024

In other words, a(n) is the minimum number of kings that can be placed on an n X n chessboard such that (i) the occupied squares form a single connected component, and (ii) every square is either occupied by a king or adjacent to one that is.

a(17) <= 67; a(18) <= 75; a(19) <= 83; a(20) <= 92.

Alexander D. Healy, Examples of (near-)optimal connected dominating sets for n <= 20.
Eric Weisstein's World of Mathematics, Connected Domination Number.
Eric Weisstein's World of Mathematics, King Graph.

Cf. A075561, A289180, A302401, A369692.

Cf. A382206 (numbers of minimum connected dominating sets).

a(13)-a(16) from Andrew Howroyd, Feb 25 2024

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

A370428 Connected domination number of the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula