A300358 -id:A300358 - cp's OEIS frontend

A303118 Array read by antidiagonals: T(m,n) = number of minimal total dominating sets in the grid graph P_m X P_n.

0, 1, 1, 2, 4, 2, 1, 4, 4, 1, 2, 16, 6, 16, 2, 4, 16, 49, 49, 16, 4, 3, 49, 66, 169, 66, 49, 3, 4, 81, 225, 576, 576, 225, 81, 4, 8, 169, 640, 2601, 2622, 2601, 640, 169, 8, 9, 324, 1681, 10000, 14400, 14400, 10000, 1681, 324, 9, 10, 625, 4641, 38416, 81055, 137641, 81055, 38416, 4641, 625, 10

Offset: 1

Andrew Howroyd, Apr 18 2018

			Table begins:
=============================================================
m\n| 1   2    3     4      5       6         7          8
---+---------------------------------------------------------
1  | 0   1    2     1      2       4         3          4 ...
2  | 1   4    4    16     16      49        81        169 ...
3  | 2   4    6    49     66     225       640       1681 ...
4  | 1  16   49   169    576    2601     10000      38416 ...
5  | 2  16   66   576   2622   14400     81055     440896 ...
6  | 4  49  225  2601  14400  137641   1081600    8185321 ...
7  | 3  81  640 10000  81055 1081600  11458758  125955729 ...
8  | 4 169 1681 38416 440896 8185321 125955729 1944369025 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimal Total Dominating Set.

Rows 1..2 are A302655, A303072.
Main diagonal is A303161.
Cf. A300358, A303111, A303293.

A303293 Array read by antidiagonals: T(m,n) = number of minimum total dominating sets in the grid graph P_m X P_n.

Original entry on oeis.org

0, 1, 1, 2, 4, 2, 1, 1, 1, 1, 1, 16, 2, 16, 1, 4, 9, 1, 1, 9, 4, 3, 1, 3, 16, 3, 1, 3, 1, 64, 4, 256, 256, 4, 64, 1, 2, 16, 4, 4, 160, 4, 4, 16, 2, 9, 1, 9, 121, 25, 25, 121, 9, 1, 9, 4, 169, 12, 2916, 268, 144, 268, 2916, 12, 169, 4

Offset: 1

Andrew Howroyd, Apr 20 2018

The minimum size of a total dominating set is the total domination number A300358(m, n).

			Table begins:
===============================================
m\n| 1  2  3    4    5     6   7    8     9
---+-------------------------------------------
1  | 0  1  2    1    1     4   3    1     2 ...
2  | 1  4  1   16    9     1  64   16     1 ...
3  | 2  1  2    1    3     4   4    9    12 ...
4  | 1 16  1   16  256     4 121 2916    25 ...
5  | 1  9  3  256  160    25 268 4225   510 ...
6  | 4  1  4    4   25   144 529 2025 10404 ...
7  | 3 64  4  121  268   529   4  441   630 ...
8  | 1 16  9 2916 4225  2025 441  256     9 ...
9  | 2  1 12   25  510 10404 630    9  1364 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.

Rows 1..2 are A302654, A303054.
Main diagonal is A303142.
Cf. A300358, A303111, A303118.

A302488 Total domination number of the n X n grid graph.

Original entry on oeis.org

0, 1, 2, 3, 6, 9, 12, 15, 20, 25, 30, 35, 42, 49, 56, 63, 72, 81, 90, 99, 110, 121, 132, 143, 156, 169, 182, 195, 210, 225, 240, 255, 272, 289, 306, 323, 342, 361, 380, 399, 420, 441, 462, 483, 506, 529, 552, 575, 600, 625, 650, 675, 702, 729, 756, 783, 812, 841, 870, 899, 930

Offset: 0

Eric W. Weisstein, Apr 08 2018

Extended to a(0) and a(1) using the formula/recurrence. The total domination number of the 1 X 1 grid graph is undefined.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Total Domination Number.
Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1,-2,1).

Main diagonal of A300358.
The four quadrasections are A002943, A016754, A002939(n+1), A000466(n+1).
Bisections are A002378 and A085046.
Cf. A303142.

R:=RealField(); [Round(((-1)^n + 2*n*(n + 2) + 4*Sin(n*Pi(R)/2) - 1)/8): n in [0..30]]; // G. C. Greubel, Apr 09 2018

Table[(-1 + (-1)^n + 2 n (2 + n) + 4 Sin[n Pi/2])/8, {n, 0, 20}]
LinearRecurrence[{2, -1, 0, 1, -2, 1}, {0, 1, 2, 3, 6, 9}, 20]
CoefficientList[Series[x (-1 - 2 x^3 + x^4)/((-1 + x)^3 (1 + x + x^2 + x^3)), {x, 0, 20}], x]

for(n=0,30, print1(round(((-1)^n + 2*n*(n + 2) + 4*sin(n*Pi/2) - 1)/8), ", ")) \\ G. C. Greubel, Apr 09 2018

a(n)=my(m=n\4); (2*m+1)*(2*m + n%4) \\ Andrew Howroyd, Aug 17 2025

a(n) = ((-1)^n + 2*n*(n + 2) + 4*sin(n*Pi/2) - 1)/8.
a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6).
G.f.: x*(1 + 2*x^3 - x^4)/((1 - x)^3*(1 + x + x^2 + x^3)).
a(4*m + r) = (2*m + 1)*(2*m + r) for 0 <= r < 4. - Charles Kusniec, Aug 16 2025
From Amiram Eldar, Aug 26 2025: (Start)
Sum_{n>=1} 1/a(n) = Pi^2/8 + 3/2.
Sum_{n>=1} (-1)^(n+1)/a(n) = Pi^2/8 - 1/2. (End)

a(0)=0 prepended and offset corrected by Andrew Howroyd, Aug 17 2025

A350823 Array read by antidiagonals: T(m,n) is the 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, 2, 3, 3, 3, 2, 2, 3, 4, 4, 3, 2, 3, 4, 4, 4, 4, 4, 3, 3, 4, 5, 6, 6, 5, 4, 3, 3, 5, 6, 7, 7, 7, 6, 5, 3, 4, 5, 7, 7, 8, 8, 7, 7, 5, 4, 4, 6, 7, 8, 9, 10, 9, 8, 7, 6, 4, 4, 6, 8, 10, 11, 11, 11, 11, 10, 8, 6, 4

Offset: 1

Andrew Howroyd, Jan 17 2022

Equivalently, the minimum number of X-pentominoes needed to cover an m X n grid.

			Table begins:
===================================
m\n | 1  2  3  4  5  6  7  8  9
----+------------------------------
  1 | 1  1  1  2  2  2  3  3  3 ...
  2 | 1  2  2  3  3  4  4  5  5 ...
  3 | 1  2  3  4  4  5  6  7  7 ...
  4 | 2  3  4  4  6  7  7  8 10 ...
  5 | 2  3  4  6  7  8  9 11 12 ...
  6 | 2  4  5  7  8 10 11 12 14 ...
  7 | 3  4  6  7  9 11 12 14 16 ...
  8 | 3  5  7  8 11 12 14 16 18 ...
  9 | 3  5  7 10 12 14 16 18 20 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph

Row 4 is A193768.
Main diagonal is A104519.
Cf. A286847, A300358, A350820.

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

T(1,n) = ceiling(n/3); T(2,n) = floor(n/2) + 1.

A303378 Array read by antidiagonals: T(m,n) = total domination number of the m X n king graph.

Original entry on oeis.org

1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 4, 3, 2, 2, 3, 4, 4, 4, 3, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 5, 4, 4, 4, 5, 6, 5, 4, 6, 6, 6, 6, 4, 5, 6, 6, 6, 5, 6, 7, 8, 7, 6, 5, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 6, 6, 6, 6, 7, 6, 6, 8, 9, 8, 9, 8, 9, 8, 6, 6, 7

Offset: 1

Andrew Howroyd, Apr 22 2018

			Table begins:
=======================================================
m\n| 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
---+---------------------------------------------------
1  | 1  2  2  2  3  4  4  4  5  6  6  6  7  8  8  8 ...
2  | 2  2  2  2  3  4  4  4  5  6  6  6  7  8  8  8 ...
3  | 2  2  2  2  3  4  4  4  5  6  6  6  7  8  8  8 ...
4  | 2  2  2  4  4  4  6  6  6  8  8  8 10 10 10 12 ...
5  | 3  3  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
6  | 4  4  4  4  6  8  8  8 10 12 12 12 14 16 16 16 ...
7  | 4  4  4  6  7  8  9 10 11 12 14 14 16 17 18 19 ...
8  | 4  4  4  6  8  8 10 12 12 14 16 16 18 20 20 22 ...
9  | 5  5  5  6  9 10 11 12 15 16 17 18 21 22 23 24 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Total Dominating Set

Main diagonal is A302401.

Cf. A300358, A303114, A303335.

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

A303118 Array read by antidiagonals: T(m,n) = number of minimal total dominating sets in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A303293 Array read by antidiagonals: T(m,n) = number of minimum total dominating sets in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A302488 Total domination number of the n X n grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A303378 Array read by antidiagonals: T(m,n) = total domination number of the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

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