A303293 -id:A303293 - cp's OEIS frontend

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

1, 2, 2, 1, 6, 1, 4, 3, 3, 4, 3, 12, 10, 12, 3, 1, 2, 29, 29, 2, 1, 8, 17, 1, 2, 1, 17, 8, 4, 2, 2, 52, 52, 2, 2, 4, 1, 20, 11, 92, 22, 92, 11, 20, 1, 13, 2, 46, 2, 13, 13, 2, 46, 2, 13, 5, 24, 1, 4, 3, 288, 3, 4, 1, 24, 5, 1, 2, 3, 324, 344, 34, 34, 344, 324, 3, 2, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The domination number of the grid graphs is tabulated in A350823.

			Table begins:
===================================
m\n | 1  2  3  4   5   6  7   8
----+------------------------------
  1 | 1  2  1  4   3   1  8   4 ...
  2 | 2  6  3 12   2  17  2  20 ...
  3 | 1  3 10 29   1   2 11  46 ...
  4 | 4 12 29  2  52  92  2   4 ...
  5 | 3  2  1 52  22  13  3 344 ...
  6 | 1 17  2 92  13 288 34   2 ...
  7 | 8  2 11  2   3  34  2  34 ...
  8 | 4 20 46  4 344   2 34  52 ...
  ...

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 276 terms from Andrew Howroyd)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Rows 1..4 are A347633, A347558, A350821, A350822.
Main diagonal is A347632.
Cf. A218354 (dominating sets), A286847 (minimal dominating sets), A303293, A350815, A350823.

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

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

Original entry on oeis.org

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.

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

Original entry on oeis.org

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

Offset: 1

Andrew Howroyd, Apr 20 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  4  4  4  6  6  6  8  8  8 10 10 10 12 ...
3  | 2  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
4  | 2  4  4  6  8  8 10 12 12 14 14 16 18 18 20 20 ...
5  | 3  4  5  8  9 10 12 14 15 16 18 20 21 22 24 26 ...
6  | 4  4  6  8 10 12 14 16 18 20 20 24 24 26 28 30 ...
7  | 4  6  7 10 12 14 15 18 20 22 24 26 27 30 32 34 ...
8  | 4  6  8 12 14 16 18 20 22 24 28 30 32 34 36 38 ...
9  | 5  6  9 12 15 18 20 22 25 28 30 32 35 38 40 42 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..435 (first 29 antidiagonals)
Alexandre Talon, Intensive use of computing resources for dominations in grids and other combinatorial problems, arXiv:2002.11615 [cs.DM], 2020. See Sec. 2.3.2.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Total Domination Number

Rows 1..2 are A004524(n+2), A302402.
Main diagonal is A302488.
Cf. A303111, A303118, A303293.

A303335 Array read by antidiagonals: T(m,n) is the number of minimum total dominating sets in the m X n king graph.

Original entry on oeis.org

0, 1, 1, 2, 6, 2, 1, 9, 9, 1, 1, 4, 8, 4, 1, 4, 8, 1, 1, 8, 4, 3, 89, 3, 35, 3, 89, 3, 1, 56, 76, 9, 9, 76, 56, 1, 2, 16, 17, 1, 1, 1, 17, 16, 2, 9, 64, 1, 130, 9, 9, 130, 1, 64, 9, 4, 780, 6, 16, 60, 8684, 60, 16, 6, 780, 4, 1, 304, 229, 1, 89, 493, 493, 89, 1, 229, 304, 1

Offset: 1

Andrew Howroyd, Apr 21 2018

The minimum size of a total dominating set is the total domination number A303378(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  6  9   4  8   89  56  16   64 ...
3  | 2  9  8   1  3   76  17   1    6 ...
4  | 1  4  1  35  9    1 130  16    1 ...
5  | 1  8  3   9  1    9  60  89   45 ...
6  | 4 89 76   1  9 8684 493   1   50 ...
7  | 3 56 17 130 60  493 208  40   32 ...
8  | 1 16  1  16 89    1  40 604    1 ...
9  | 2 64  6   1 45   50  32   1 1192 ...
...

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

Rows 1..2 are A302654, A350817.
Main diagonal is A303156.
Cf. A303114, A303293, A303378, A332390, A350815.

A302654 Number of minimum total dominating sets in the n-path graph.

Original entry on oeis.org

0, 1, 2, 1, 1, 4, 3, 1, 2, 9, 4, 1, 3, 16, 5, 1, 4, 25, 6, 1, 5, 36, 7, 1, 6, 49, 8, 1, 7, 64, 9, 1, 8, 81, 10, 1, 9, 100, 11, 1, 10, 121, 12, 1, 11, 144, 13, 1, 12, 169, 14, 1, 13, 196, 15, 1, 14, 225, 16, 1, 15, 256, 17, 1, 16, 289, 18, 1, 17, 324, 19, 1, 18, 361, 20, 1

Offset: 1

Eric W. Weisstein, Apr 11 2018

Colin Barker, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
Eric Weisstein's World of Mathematics, Path Graph.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,3,0,0,0,-3,0,0,0,1).

Row 1 of A303293.

Cf. A302653, A302655.

Table[Piecewise[{{1, Mod[n, 4] == 0}, {((n + 2)/4)^2, Mod[n, 4] == 2}, {(n - 1)/4, Mod[n, 4] == 1}, {(n + 5)/4, Mod[n, 4] == 3}}], {n, 20}]
Table[((-1)^n (n - 2)^2 + (6 + n)^2 - 2 (n - 2) (n + 6) Cos[n Pi/2] - 48 Sin[n Pi/2])/64, {n, 20}]
LinearRecurrence[{0, 0, 0, 3, 0, 0, 0, -3, 0, 0, 0, 1}, {0, 1, 2, 1, 1, 4, 3, 1, 2, 9, 4, 1}, 20]

concat(0, Vec(x^2*(1 + 2*x + x^2 + x^3 + x^4 - 3*x^5 - 2*x^6 - x^7 + x^9 + x^10) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3) + O(x^70))) \\ Colin Barker, Dec 25 2019

a(n) = ((-1)^n*(n - 2)^2 + (6 + n)^2 - 2*(n - 2)*(n + 6)*cos(n*Pi/2) - 48*sin(n*Pi/2))/6.
a(n) = 3*a(n-4) - 3*a(n-8) + a(n-12).
G.f.: x^2*(1 + 2*x + x^2 + x^3 + x^4 - 3*x^5 - 2*x^6 - x^7 + x^9 + x^10) / ((1 - x)^3*(1 + x)^3*(1 + x^2)^3). - Colin Barker, Dec 25 2019
E.g.f.: ((12 + x^2)*cos(x) + (20 + 8*x + x^2)*cosh(x) + (5*x - 24)*sin(x) + (16 + 5*x)*sinh(x) - 32)/32. - Stefano Spezia, Jun 10 2025

A303054 Number of minimum total dominating sets in the n-ladder graph.

Original entry on oeis.org

1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1, 676, 49, 1, 1156, 64, 1, 1849, 81, 1, 2809, 100, 1, 4096, 121, 1, 5776, 144, 1, 7921, 169, 1, 10609, 196, 1, 13924, 225, 1, 17956, 256, 1, 22801, 289, 1, 28561, 324, 1, 35344, 361, 1, 43264, 400, 1, 52441

Offset: 1

Eric W. Weisstein, Apr 17 2018

Each vertex can dominate up to three others. A ladder with a length that is an exact multiple of three can be dominated in only one way with 2n/3 vertices. - Andrew Howroyd, Apr 21 2018

			From _Andrew Howroyd_, Apr 21 2018: (Start)
a(9) = 1 because there is only one arrangement of 6 vertices that is totally dominating and no set with fewer vertices can be totally dominating:
  .__o__.__.__o__.__.__o__.
     |        |        |
  .__o__.__.__o__.__.__o__.
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Ladder Graph.
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
Index entries for linear recurrences with constant coefficients, signature (0,0,5,0,0,-10,0,0,10,0,0,-5,0,0,1).

Row 2 of A303293.

Cf. A302402, A303072.

Table[Piecewise[{{1, Mod[n, 3] == 0}, {((n^2 + 13 n + 4)/18)^2, Mod[n, 3] == 1}, {((n + 4)/3)^2, Mod[n, 3] == 2}}], {n, 58}] (* Eric W. Weisstein, Apr 23 2018 and Michael De Vlieger, Apr 21 2018 *)
Table[(916 + 392 n + 213 n^2 + 26 n^3 + n^4 - (-56 + 392 n + 213 n^2 + 26 n^3 + n^4) Cos[2 n Pi/3] + Sqrt[3] (-20 + 7 n + n^2) (28 + 19 n + n^2) Sin[2 n Pi/3])/972, {n, 20}] (* Eric W. Weisstein, Apr 23 2018 *)
LinearRecurrence[{0, 0, 5, 0, 0, -10, 0, 0, 10, 0, 0, -5, 0, 0, 1}, {1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1}, 20] (* Eric W. Weisstein, Apr 23 2018 *)
CoefficientList[Series[(-1 - 4 x - x^2 - 11 x^3 + 11 x^4 + 4 x^5 + 6 x^6 - 11 x^7 - 6 x^8 + x^9 + 5 x^10 + 4 x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5, {x, 0, 20}], x] (* Eric W. Weisstein, Apr 23 2018 *)

a(n)={if(n%3==0, 1, if(n%3==1, (n^2 + 13*n + 4)/18, (n + 4)/3))^2} \\ Andrew Howroyd, Apr 21 2018

Vec(x*(1 + 4*x + x^2 + 11*x^3 - 11*x^4 - 4*x^5 - 6*x^6 + 11*x^7 + 6*x^8 - x^9 - 5*x^10 - 4*x^11 + x^12 + x^13 + x^14) / ((1 - x)^5*(1 + x + x^2)^5) + O(x^60)) \\ Colin Barker, Apr 23 2018

a(n) = 1 for n mod 3 = 0
     = ((n^2 + 13*n + 4)/18)^2 for n mod 3 = 1
     = ((n + 4)/3)^2 for n mod 3 = 2.
G.f.: x*(-1 - 4*x - x^2 - 11*x^3 + 11*x^4 + 4*x^5 + 6*x^6 - 11*x^7 - 6*x^8 + x^9 + 5*x^10 + 4*x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5.
a(n) = 5*a(n-3) - 10*a(n-6) + 10*a(n-9) - 5*a(n-12) + a(n-15) for n>15. - Colin Barker, Apr 23 2018

Terms a(14) and beyond from Andrew Howroyd, Apr 21 2018

A303142 Number of minimum total dominating sets in the n X n grid graph.

Original entry on oeis.org

0, 4, 2, 16, 160, 144, 4, 256, 1364, 484, 6, 784, 5032, 1444, 8, 2116, 12972, 3364, 10, 4624, 27376, 6724, 12, 8836, 50820, 12100, 14, 15376, 86264, 20164

Offset: 1

Eric W. Weisstein, Apr 19 2018

Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.

Main diagonal of A303293.

Cf. A133793, A302488, A303161.

a(6)-a(30) from Andrew Howroyd, Apr 22 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

A303335 Array read by antidiagonals: T(m,n) is the number of minimum total dominating sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A302654 Number of minimum total dominating sets in the n-path graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A303054 Number of minimum total dominating sets in the n-ladder graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A303142 Number of minimum total dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions