A303335 -id:A303335 - cp's OEIS frontend

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

1, 2, 2, 1, 4, 1, 4, 2, 2, 4, 3, 16, 1, 16, 3, 1, 12, 4, 4, 12, 1, 8, 4, 3, 256, 3, 4, 8, 4, 64, 1, 144, 144, 1, 64, 4, 1, 32, 8, 16, 79, 16, 8, 32, 1, 13, 8, 4, 4096, 9, 9, 4096, 4, 8, 13, 5, 208, 1, 1024, 1656, 1, 1656, 1024, 1, 208, 5, 1, 80, 13, 64, 408, 64, 64, 408, 64, 13, 80, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The minimum size of a dominating set is the domination number which in the case of an m X n king graph is given by (ceiling(m/3) * ceiling(n/3)).

			Table begins:
============================================
m\n | 1  2  3    4    5   6      7     8
----+---------------------------------------
  1 | 1  2  1    4    3   1      8     4 ...
  2 | 2  4  2   16   12   4     64    32 ...
  3 | 1  2  1    4    3   1      8     4 ...
  4 | 4 16  4  256  144  16   4096  1024 ...
  5 | 3 12  3  144   79   9   1656   408 ...
  6 | 1  4  1   16    9   1     64    16 ...
  7 | 8 64  8 4096 1656  64 243856 29744 ...
  8 | 4 32  4 1024  408  16  29744  3600 ...
     ...

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, King Graph
Eric Weisstein's World of Mathematics, Minimum Dominating Set

Rows 1..3 are A347633, A350816, A347633.
Main diagonal is A347554.
Cf. A075561, A218663 (dominating sets), A286849 (minimal dominating sets), A303335, A350818, A350819.

T(n,m) = T(m,n).
T(3*m, 3*n) = 1; T(3*m+1, 3*n) = (m^2 + 5*m + 2)^n; T(3*m+2, 3*n) = (m+2)^n.
T(3*m-1, 3*n-1) = A350819(m, n).

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).

A303156 Number of minimum total dominating sets in the n X n king graph.

Original entry on oeis.org

0, 6, 8, 35, 1, 8684, 208, 604, 1192, 276696, 1362, 2, 2986, 32, 38772, 28520, 441984, 1024, 5047188

Offset: 1

Eric W. Weisstein, Apr 19 2018

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

Main diagonal of A303335.

Cf. A302401, A303116, A332391.

a(6)-a(19) from Andrew Howroyd, Apr 21 2018

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.

A350817 Number of minimum total dominating sets in the 2 X n king graph.

Original entry on oeis.org

1, 6, 9, 4, 8, 89, 56, 16, 64, 780, 304, 64, 384, 5472, 1536, 256, 2048, 33920, 7424, 1024, 10240, 194304, 34816, 4096, 49152, 1053696, 159744, 16384, 229376, 5488640, 720896, 65536, 1048576, 27721728, 3211264, 262144, 4718592, 136642560, 14155776, 1048576

Offset: 1

Andrew Howroyd, Jan 17 2022

Eric Weisstein's World of Mathematics, King Graph.
Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,12,0,0,0,-48,0,0,0,64).

Row 2 of A303335.

Cf. A350816.

LinearRecurrence[{0, 0, 0, 12, 0, 0, 0, -48, 0, 0, 0, 64}, {1, 6, 9, 4, 8, 89, 56, 16, 64, 780, 304, 64, 384}, 40] (* Michael De Vlieger, Jan 19 2022 *)

Vec((1 + 6*x + 9*x^2 + 4*x^3 - 4*x^4 + 17*x^5 - 52*x^6 - 32*x^7 + 16*x^8 + 64*x^10 + 64*x^11 - 64*x^12)/((1 - 2*x^2)^3*(1 + 2*x^2)^3) + O(x^40))

a(n)={my(k=n\4); 4^k*if(n%2, if(n%4==1, (k==0) + 2*k, 5*k + 9), if(n%4==0, 1, (k + 1)*(41*k + 48)/8))}

a(n) = 12*a(n-4) - 48*a(n-8) + 64*a(n-12) for n > 13.
G.f.: x*(1 + 6*x + 9*x^2 + 4*x^3 - 4*x^4 + 17*x^5 - 52*x^6 - 32*x^7 + 16*x^8 + 64*x^10 + 64*x^11 - 64*x^12)/((1 - 2*x^2)^3*(1 + 2*x^2)^3).
a(4*k) = 4^k; a(4*k+1) = 2*k*4^k for k > 0; a(4*k+2) = (k + 1)*(41*k + 48)*4^k/8; a(4*k+3) = (5*k + 9)*4^k.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A303156 Number of minimum total dominating sets in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

A350817 Number of minimum total dominating sets in the 2 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula