login
Connected domination number of the n X n grid graph.
2

%I #31 Mar 06 2024 21:48:05

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

%N Connected domination number of the n X n grid graph.

%H Alexander D. Healy, <a href="/A369692/a369692.pdf">Examples of (near-)optimal dominating sets for n <= 12</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedDominationNumber.html">Connected Domination Number</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>.

%F 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

%e From _Andrew Howroyd_, Mar 06 2024: (Start)

%e a(16) = 95 = 16 + 5*14 + 4*2 + 1.

%e . . . . . . . . . . . . . . . .

%e X X X X X X X X X X X X X X X X

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X X X

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X X X

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X X X

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X X X

%e . X . . X . . X . . X . . X . .

%e . X . . X . . X . . X . . X X .

%e (End)

%Y Cf. A104519, A287690, A302488, A370428.

%K nonn,more

%O 1,2

%A _Alexander D. Healy_, Feb 25 2024

%E a(10)-a(16) from _Andrew Howroyd_, Feb 25 2024