A350816 -id:A350816 - 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).

A347633 Number of minimum dominating sets in the path graph P_n.

Original entry on oeis.org

1, 2, 1, 4, 3, 1, 8, 4, 1, 13, 5, 1, 19, 6, 1, 26, 7, 1, 34, 8, 1, 43, 9, 1, 53, 10, 1, 64, 11, 1, 76, 12, 1, 89, 13, 1, 103, 14, 1, 118, 15, 1, 134, 16, 1, 151, 17, 1, 169, 18, 1, 188, 19, 1, 208, 20, 1, 229, 21, 1, 251, 22, 1, 274, 23, 1, 298, 24, 1, 323

Offset: 1

Eric W. Weisstein, Sep 09 2021

nonn

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

Row 1 of A350815 and A350820.

Cf. A347538, A347558, A350816.

Table[Piecewise[{{1, Mod[n, 3] == 0}, {(n^2 + 13 n + 4)/18, Mod[n, 3] == 1}, {(n + 4)/3, Mod[n, 3] == 2}}], {n, 20}]
LinearRecurrence[{0, 0, 3, 0, 0, -3, 0, 0, 1}, {1, 2, 1, 4, 3, 1, 8, 4, 1}, 20]
CoefficientList[Series[-(1 + 2 x + x^2 + x^3 - 3 x^4 - 2 x^5 - x^6 + x^7 + x^8)/((-1 + x)^3 (1 + x + x^2)^3), {x, 0, 20}], x]

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

a(n) = 1               for n = 0 (mod 3)
       (n^2+13*n+4)/18 for n = 1 (mod 3)
       (n+4)/3         for n = 2 (mod 3).
a(n) = 3*a(n-3)-3*a(n-6)+a(n-9) for n > 9.
G.f.: -(x*(1+2*x+x^2+x^3-3*x^4-2*x^5-x^6+x^7+x^8))/((-1+x)^3*(1+x+x^2)^3).

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

A347633 Number of minimum dominating sets in the path graph P_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula