A303118 -id:A303118 - cp's OEIS frontend

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

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.

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.

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

Original entry on oeis.org

0, 1, 1, 3, 9, 3, 4, 25, 25, 4, 5, 81, 161, 81, 5, 9, 289, 961, 961, 289, 9, 16, 961, 6235, 11236, 6235, 961, 16, 25, 3249, 39601, 137641, 137641, 39601, 3249, 25, 39, 11025, 251433, 1677025, 3270375, 1677025, 251433, 11025, 39

Offset: 1

Andrew Howroyd, Apr 18 2018

Equivalently, the number of n X m binary matrices with every element adjacent to some 0 horizontally or vertically.

			Table begins:
=======================================================================
m\n|  1    2      3        4          5            6              7
---|-------------------------------------------------------------------
1  |  0    1      3        4          5            9             16 ...
2  |  1    9     25       81        289          961           3249 ...
3  |  3   25    161      961       6235        39601         251433 ...
4  |  4   81    961    11236     137641      1677025       20430400 ...
5  |  5  289   6235   137641    3270375     76405081     1783064069 ...
6  |  9  961  39601  1677025   76405081   3416753209   152598828321 ...
7  | 16 3249 251433 20430400 1783064069 152598828321 13057656650476 ...
...

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

Rows 1..2 are A195971(n-1), A141583(n+1).
Main diagonal is A133793.
Cf. A218354 (dominating sets), A291872 (connected dominating sets).
Cf. A303114 (king graph), A303118 (minimal total dominating sets).

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

Original entry on oeis.org

0, 1, 1, 2, 6, 2, 1, 10, 10, 1, 2, 15, 20, 15, 2, 4, 52, 52, 52, 52, 4, 3, 105, 179, 141, 179, 105, 3, 4, 175, 418, 801, 801, 418, 175, 4, 8, 481, 1167, 2950, 7770, 2950, 1167, 481, 8, 9, 1028, 3498, 9792, 34790, 34790, 9792, 3498, 1028, 9, 10, 2000, 9074, 47527, 184318, 204372, 184318, 47527, 9074, 2000, 10

Offset: 1

Andrew Howroyd, Feb 10 2020

			Array begins:
================================================================
m\n | 1   2    3     4       5        6         7          8
----+-----------------------------------------------------------
  1 | 0   1    2     1       2        4         3          4 ...
  2 | 1   6   10    15      52      105       175        481 ...
  3 | 2  10   20    52     179      418      1167       3498 ...
  4 | 1  15   52   141     801     2950      9792      47527 ...
  5 | 2  52  179   801    7770    34790    184318    1305358 ...
  6 | 4 105  418  2950   34790   204372   1593094   14720683 ...
  7 | 3 175 1167  9792  184318  1593094  16260853  231301551 ...
  8 | 4 481 3498 47527 1305358 14720683 231301551 4570906041 ...
  ...

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

Rows 1..4 are A302655, A332392, A332393, A332394.
Main diagonal is A332391.
Cf. A286849, A303114, A303118, A303335, A303378.

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

A302655 Number of minimal total dominating sets in the n-path graph.

Original entry on oeis.org

0, 1, 2, 1, 2, 4, 3, 4, 8, 9, 10, 16, 21, 25, 36, 49, 60, 81, 112, 144, 189, 256, 336, 441, 592, 784, 1029, 1369, 1820, 2401, 3182, 4225, 5586, 7396, 9815, 12996, 17200, 22801, 30210, 40000, 53001, 70225, 93000, 123201, 163240, 216225, 286416, 379456, 502665

Offset: 1

Eric W. Weisstein, Apr 11 2018

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

Row 1 of A303118.

Cf. A000931, A300738, A302654.

Table[If[Mod[n, 2] == 0, (RootSum[-1 - # + #^3 &, #^(n/2 + 5) (5 - 6 # + 4 #^2) &]/23)^2, (RootSum[-1 + # - 2 #^2 + #^3 &, #^((n - 1)/2) (4 - 2 # + 5 #^2) &] + RootSum[-1 + #^2 + #^3 &, #^((n - 1)/2) (-5 + 6 # + 3 #^2) &])/23], {n, 50}]
LinearRecurrence[{0, 0, 1, 1, 1, 1, 0, -1, -1}, {0, 1, 2, 1, 2, 4, 3, 4, 8}, 50]
CoefficientList[Series[(x (1 + 2 x + x^2 + x^3 + x^4 - x^5 - 2 x^6 - x^7))/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9), {x, 0, 50}], x]

concat([0],Vec(x^2*(1 + 2*x + x^2 + x^3 + x^4 - x^5 - 2*x^6 - x^7)/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9) + O(x^50))) \\ Andrew Howroyd, Apr 15 2018

From Andrew Howroyd, Apr 15 2018: (Start)
a(n) = a(n-3) + a(n-4) + a(n-5) + a(n-6) - a(n-8) - a(n-9) for n > 9.
G.f.: x^2*(1 + 2*x + x^2 + x^3 + x^4 - x^5 - 2*x^6 - x^7)/(1 - x^3 - x^4 - x^5 - x^6 + x^8 + x^9).
a(2*n) = A000931(n+5)^2. (End)

Terms a(20) and beyond from Andrew Howroyd, Apr 15 2018

A303072 Number of minimal total dominating sets in the n-ladder graph.

Original entry on oeis.org

1, 4, 4, 16, 16, 49, 81, 169, 324, 625, 1296, 2401, 4900, 9409, 18769, 36481, 71824, 141376, 276676, 544644, 1067089, 2099601, 4116841, 8088336, 15880225, 31181056, 61230625, 120209296, 236083225, 463497841, 910168561, 1787091076, 3509140644, 6890328064, 13529411856

Offset: 1

Eric W. Weisstein, Apr 18 2018

Eric Weisstein's World of Mathematics, Ladder Graph.
Eric Weisstein's World of Mathematics, Minimal Total Dominating Set.
Index entries for linear recurrences with constant coefficients, signature (-1,1,3,7,8,2,6,6,0,0,-6,-6,-2,-8,-7,-3,-1,1,1).

Row 2 of A303118.

Cf. A290379, A302402, A303054.

Table[(RootSum[1 - #^2 - #^3 - #^4 + #^6 &, (9 - 18 #^2 + 23 #^3 - 3 #^4 + 32 #^5) #^n &]/229)^2, {n, 40}]
LinearRecurrence[{-1, 1, 3, 7, 8, 2, 6, 6, 0, 0, -6, -6, -2, -8, -7, -3, -1, 1, 1}, {1, 4, 4, 16, 16, 49, 81, 169,324, 625, 1296, 2401, 4900, 9409, 18769, 36481, 71824, 141376, 276676}, 40]
CoefficientList[Series[(-1 - 5 x - 7 x^2 - 13 x^3 - 9 x^4 - x^5 - 4 x^6 + 5 x^7 + 13 x^8 + 14 x^9 + 21 x^10 + 15 x^11 + 12 x^12 + 15 x^13 + 9 x^14 + 3 x^15 - 2 x^17 - x^18)/(-1 - x + x^2 + 3 x^3 + 7 x^4 + 8 x^5 + 2 x^6 + 6 x^7 + 6 x^8 - 6 x^11 - 6 x^12 - 2 x^13 - 8 x^14 - 7 x^15 - 3 x^16 - x^17 + x^18 + x^19), {x, 0, 40}], x]

a(n) = A253412(n)^2.

G.f.: x*(-1 - 5*x - 7*x^2 - 13*x^3 - 9*x^4 - x^5 - 4*x^6 + 5*x^7 + 13*x^8 + 14*x^9 + 21*x^10 + 15*x^11 + 12*x^12 + 15*x^13 + 9*x^14 + 3*x^15 - 2*x^17 - x^18)/(-1 - x + x^2 + 3*x^3 + 7*x^4 + 8*x^5 + 2*x^6 + 6*x^7 + 6*x^8 - 6*x^11 - 6*x^12 - 2*x^13 - 8*x^14 - 7*x^15 - 3*x^16 - x^17 + x^18 + x^19).

A303161 Number of minimal total dominating sets in the n X n grid graph.

Original entry on oeis.org

0, 4, 6, 169, 2622, 137641, 11458758, 1944369025, 692690245830, 490393052832400, 695395811259688914, 1963720302048546357904, 11300709997961358290597645, 129580789221471473285725965124, 2990581397819168926985646623641461

Offset: 1

Eric W. Weisstein, Apr 19 2018

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

Main diagonal of A303118.

Cf. A133793, A290382, A303142.

a(n) = A303118(n,n).

a(7)-a(15) from Andrew Howroyd, Apr 20 2018

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A302655 Number of minimal total dominating sets in the n-path graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A303072 Number of minimal total dominating sets in the n-ladder graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A303161 Number of minimal total dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions