A370428 -id:A370428 - cp's OEIS frontend

A369692 Connected domination number of the n X n grid graph.

1, 2, 3, 7, 11, 14, 20, 26, 30, 39, 47, 52, 64, 74, 80, 95

Offset: 1

Alexander D. Healy, Feb 25 2024

			From _Andrew Howroyd_, Mar 06 2024: (Start)
a(16) = 95 = 16 + 5*14 + 4*2 + 1.
  . . . . . . . . . . . . . . . .
  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 . . 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 . .
  . 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 . . X . . X . . X . . X X .
(End)

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

Cf. A104519, A287690, A302488, A370428.

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

a(3*n) <= n*(3*n+1); a(3*n-1) <= 3*n^2 - 1; a(3*n-2) <= (n-1)*(3*n+1). Conjecturally these inequalities hold with equality for n > 1. - Andrew Howroyd, Mar 06 2024

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

A382206 Number of minimum connected dominating sets in the n X n king graph.

Original entry on oeis.org

1, 4, 1, 21, 1, 21, 843, 720, 556841, 99357, 458, 32, 3600, 30580044, 826720, 4

Offset: 1

Eric W. Weisstein, Mar 18 2025

a(1)-a(8) computed with ILP based on a Mathematica implementation by Stan Wagon using an idea from Rob Pratt.

Eric Weisstein's World of Mathematics, Connected Dominating Set.
Eric Weisstein's World of Mathematics, King Graph.
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 1 to 6
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 7
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 8
Eric W. Weisstein, Symmetrically inequivalent minimum configurations with multiplicities for n = 16

Cf. A289180, A347554, A381730.

Cf. A370428 (connected domination numbers).

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

cp's OEIS Frontend

A369692 Connected domination number of the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions