A350815 -id:A350815 - cp's OEIS frontend

A350819 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the 2m X 2n king graph.

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 79, 32, 1, 1, 80, 408, 408, 80, 1, 1, 192, 1847, 3600, 1847, 192, 1, 1, 448, 7698, 26040, 26040, 7698, 448, 1, 1, 1024, 30319, 166368, 281571, 166368, 30319, 1024, 1, 1, 2304, 114606, 976640, 2580754, 2580754, 976640, 114606, 2304, 1

Offset: 0

Andrew Howroyd, Jan 17 2022

Number of ways to tile a (2m+1) X (2n+1) board with m*n 2 X 2 tiles and 2m+2n+1 1 X 1 tiles.

For m,n > 0, T(m,n) is the number of minimum dominating sets in the (3m-1) X (3n-1) king graph.

			Table begins:
=============================================
m\n | 0   1    2      3       4        5
----+----------------------------------------
  0 | 1   1    1      1       1        1 ...
  1 | 1   4   12     32      80      192 ...
  2 | 1  12   79    408    1847     7698 ...
  3 | 1  32  408   3600   26040   166368 ...
  4 | 1  80 1847  26040  281571  2580754 ...
  5 | 1 192 7698 166368 2580754 32572756 ...
  ...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Rows 0..12 are A000012, A001787(n+1), A061593, A061594, A173782, A173783, A174154, A174155, A174558, A195648, A195649, A195650, A195651.
Main diagonal is A018807.
Cf. A350815, A350818.

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

T(m,n) = A350818(2*m, 2*n) = A350815(3*m-1, 3*n-1).

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

Original entry on oeis.org

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

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.

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

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

Original entry on oeis.org

2, 4, 2, 16, 12, 4, 64, 32, 8, 208, 80, 16, 608, 192, 32, 1664, 448, 64, 4352, 1024, 128, 11008, 2304, 256, 27136, 5120, 512, 65536, 11264, 1024, 155648, 24576, 2048, 364544, 53248, 4096, 843776, 114688, 8192, 1933312, 245760, 16384, 4390912, 524288, 32768

Offset: 1

Andrew Howroyd, Jan 17 2022

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

Row 2 of A350815.

Cf. A000079, A001787, A076616, A347558, A347633.

Vec(2*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3 + O(x^45))

a(n) = {my(t=n\3); 2^t*if(n%3==0, 1, if(n%3==1, t^2 + 5*t + 2, 2*t + 4))}

a(n) = 6*a(n-3) - 12*a(n-6) + 8*a(n-9) for n > 9.
G.f.: 2*x*(1 - x)*(1 + 3*x + 4*x^2 + 6*x^3 - 4*x^5 - 8*x^6 - 4*x^7)/(1 - 2*x^3)^3.
a(3*n) = 2^n; a(3*n+1) = (n^2 + 5*n + 2)*2^n; a(3*n+2) = (n + 2)*2^(n+1).
a(3*n) = A000079(n); a(3*n+1) = A076616(n+3); a(3*n+2) = A001787(n+2).

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

Original entry on oeis.org

1, 4, 1, 256, 79, 1, 243856, 3600, 1, 581571283, 281585, 1, 2722291223553, 32581328, 1, 21706368614058886, 5112264019, 1, 268740319616196074546, 1028516654620, 1, 4839916638142874877046813

Offset: 1

Eric W. Weisstein, Sep 06 2021

a(3*n) = 1 for all n, since the 3n X 3n king graph has domination number n^2 and the only way to achieve this is if each of the n^2 kings is placed in the middle of its own 3 X 3 square.

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
Eric W. Weisstein, Unique minimum dominating set on a 3n X 3n king graph

Main diagonal of A350815.

Cf. A075561 (domination number of the n X n king graph), A133791, A286881.

a(7)-a(12) from Andrew Howroyd, Jan 17 2022

a(13)-a(22) from Stephan Mertens, Aug 18 2024

A350818 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the m X n king graph.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 4, 1, 1, 1, 3, 4, 4, 3, 1, 1, 1, 12, 1, 12, 1, 1, 1, 4, 8, 9, 9, 8, 4, 1, 1, 1, 32, 1, 79, 1, 32, 1, 1, 1, 5, 16, 16, 27, 27, 16, 16, 5, 1, 1, 1, 80, 1, 408, 1, 408, 1, 80, 1, 1, 1, 6, 32, 25, 81, 64, 64, 81, 25, 32, 6, 1

Offset: 0

Andrew Howroyd, Jan 17 2022

The maximum size of an independent set is the independence number which in the case of an m X n king graph is given by ceiling(m/2)*ceiling(n/2).

			Table begins:
=============================================
m\n | 0 1  2  3    4   5     6   7      8
----+----------------------------------------
  0 | 1 1  1  1    1   1     1   1      1 ...
  1 | 1 1  2  1    3   1     4   1      5 ...
  2 | 1 2  4  4   12   8    32  16     80 ...
  3 | 1 1  4  1    9   1    16   1     25 ...
  4 | 1 3 12  9   79  27   408  81   1847 ...
  5 | 1 1  8  1   27   1    64   1    125 ...
  6 | 1 4 32 16  408  64  3600 256  26040 ...
  7 | 1 1 16  1   81   1   256   1    625 ...
  8 | 1 5 80 25 1847 125 26040 625 281571 ...
  ...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximum Independent Vertex Set

Cf. A018807, A245013, A332347, A350815, A350819.

T(m,n) = T(n,m).
T(2*m+1, 2*n+1) = 1.
T(2*m, 2*n+1) = (1+m)^(1+n).
T(2*m, 2*n) = A350819(m, n).

cp's OEIS Frontend

A350819 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the 2m X 2n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A350818 Array read by antidiagonals: T(m,n) is the number of maximum independent sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula