A350820 -id:A350820 - cp's OEIS frontend

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

2, 6, 3, 12, 2, 17, 2, 20, 2, 24, 2, 28, 2, 32, 2, 36, 2, 40, 2, 44, 2, 48, 2, 52, 2, 56, 2, 60, 2, 64, 2, 68, 2, 72, 2, 76, 2, 80, 2, 84, 2, 88, 2, 92, 2, 96, 2, 100, 2, 104, 2, 108, 2, 112, 2, 116, 2, 120, 2, 124, 2, 128, 2, 132, 2, 136, 2, 140, 2, 144, 2

Offset: 1

Eric W. Weisstein, Sep 06 2021

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

Row 2 of A350820.

Cf. A347634.

Join[{2, 6, 3, 12, 2, 17}, LinearRecurrence[{0, 2, 0, -1}, {2, 20, 2, 24}, 20]]
CoefficientList[Series[(2 + 6 x - x^2 - 2 x^4 - x^5 + x^6 - 2 x^7 + x^9)/((-1 + x)^2 (1 + x)^2), {x, 0, 20}], x]

a(n)={if(n%2, 1, n+2)*2 + if(n<=6, [0,-2,1,0,0,1][n])} \\ Andrew Howroyd, Jan 18 2022

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

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

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

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 4, 4, 3, 2, 3, 4, 4, 4, 4, 4, 3, 3, 4, 5, 6, 6, 5, 4, 3, 3, 5, 6, 7, 7, 7, 6, 5, 3, 4, 5, 7, 7, 8, 8, 7, 7, 5, 4, 4, 6, 7, 8, 9, 10, 9, 8, 7, 6, 4, 4, 6, 8, 10, 11, 11, 11, 11, 10, 8, 6, 4

Offset: 1

Andrew Howroyd, Jan 17 2022

Equivalently, the minimum number of X-pentominoes needed to cover an m X n grid.

			Table begins:
===================================
m\n | 1  2  3  4  5  6  7  8  9
----+------------------------------
  1 | 1  1  1  2  2  2  3  3  3 ...
  2 | 1  2  2  3  3  4  4  5  5 ...
  3 | 1  2  3  4  4  5  6  7  7 ...
  4 | 2  3  4  4  6  7  7  8 10 ...
  5 | 2  3  4  6  7  8  9 11 12 ...
  6 | 2  4  5  7  8 10 11 12 14 ...
  7 | 3  4  6  7  9 11 12 14 16 ...
  8 | 3  5  7  8 11 12 14 16 18 ...
  9 | 3  5  7 10 12 14 16 18 20 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Domination Number
Eric Weisstein's World of Mathematics, Grid Graph

Row 4 is A193768.
Main diagonal is A104519.
Cf. A286847, A300358, A350820.

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

T(1,n) = ceiling(n/3); T(2,n) = floor(n/2) + 1.

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

Original entry on oeis.org

1, 6, 10, 2, 22, 288, 2, 52, 32, 4, 32, 21600, 18, 540360, 34528, 100406, 70266144, 1380216154, 1682689266, 77900162, 233645826, 200997249200

Offset: 1

Eric W. Weisstein, Sep 09 2021

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

Main diagonal of A350820.

Cf. A104519 (domination number), A133515 (dominating sets), A290382 (minimal dominating sets).

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

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

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

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 1, 1, 1, 1, 1, 7, 2, 7, 1, 1, 8, 1, 1, 8, 1, 1, 8, 1, 16, 1, 8, 1, 1, 8, 1, 62, 62, 1, 8, 1, 1, 8, 1, 10, 126, 10, 1, 8, 1, 1, 8, 1, 48, 11, 11, 48, 1, 8, 1, 1, 8, 1, 224, 448, 24, 448, 224, 1, 8, 1, 1, 8, 1, 8, 744, 13, 13, 744, 8, 1, 8, 1

Offset: 1

Andrew Howroyd, Mar 19 2025

			Table begins:
================================================
m\n  | 1 2 3   4    5  6    7     8  9    10 ...
-----+------------------------------------------
   1 | 1 2 1   1    1  1    1     1  1     1 ...
   2 | 2 4 1   7    8  8    8     8  8     8 ...
   3 | 1 1 2   1    1  1    1     1  1     1 ...
   4 | 1 7 1  16   62 10   48   224  8    80 ...
   5 | 1 8 1  62  126 11  448   744  8  1898 ...
   6 | 1 8 1  10   11 24   13    14 15    16 ...
   7 | 1 8 1  48  448 13  800  6408  8  5240 ...
   8 | 1 8 1 224  744 14 6408 16288  8 82128 ...
   9 | 1 8 1   8    8 15    8     8 16     8 ...
  10 | 1 8 1  80 1898 16 5240 82128  8 87216 ...
  ...

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

Main diagonal is A381730.

Cf. A291872, A350820, A381475.

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

A375566 Array read by antidiagonals: T(m,n) = number of minimum dominating sets in the stacked prism graph C_m X P_n.

Original entry on oeis.org

1, 2, 2, 1, 6, 3, 4, 3, 9, 6, 3, 12, 34, 4, 5, 1, 2, 123, 4, 10, 3, 8, 17, 3, 16, 5, 51, 14, 4, 2, 18, 28, 290, 18, 14, 8, 1, 20, 93, 76, 320, 6, 63, 4, 3, 13, 2, 438, 164, 265, 171, 14, 4, 18, 25, 5, 24, 3, 396, 255, 36, 91, 24, 9, 120, 11, 1, 2, 27, 904, 250, 6, 1526, 60, 2052, 25, 22, 3

Offset: 1

Stephan Mertens, Aug 19 2024

			Table starts:
====================================
m\n |   1   2   3    4    5    6 ...
----+-------------------------------
  1 |   1   2   1    4    3    1 ...
  2 |   2   6   3   12    2   17 ...
  3 |   3   9  34  123    3   18 ...
  4 |   6   4   4   16   28   76 ...
  5 |   5  10   5  290  320  265 ...
 ...

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

Main diagonal is A375569.
Rows 1..2 are A347633, A347558.
Column 1 is A347538, column 2 is essentially A347634.
Cf. A286514, A350820, A375603.

A350821 Number of minimum dominating sets in the grid graph P_3 X P_n.

Original entry on oeis.org

1, 3, 10, 29, 1, 2, 11, 46, 1, 3, 12, 60, 1, 4, 16, 78, 1, 5, 21, 103, 1, 6, 27, 134, 1, 7, 34, 172, 1, 8, 42, 218, 1, 9, 51, 273, 1, 10, 61, 338, 1, 11, 72, 414, 1, 12, 84, 502, 1, 13, 97, 603, 1, 14, 111, 718, 1, 15, 126, 848, 1, 16, 142, 994, 1, 17, 159, 1157, 1, 18

Offset: 1

Andrew Howroyd, Jan 17 2022

nonn

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

Row 3 of A350820.

Cf. A347633, A347558.

a(n) = 4*a(n-4) - 6*a(n-8) + 4*a(n-12) - a(n-16) for n > 28.

A350822 Number of minimum dominating sets in the grid graph P_4 X P_n.

Original entry on oeis.org

4, 12, 29, 2, 52, 92, 2, 4, 324, 2, 10, 8, 2, 16, 32, 18, 22, 74, 90, 60, 134, 270, 258, 276, 612, 888, 852, 1298, 2382, 2886, 3278, 5590, 8538, 9902, 13444, 22100, 29864, 36526, 54578, 82602, 106156, 141074, 213858, 301224, 389912, 550584, 811542, 1098516, 1471482, 2126568

Offset: 1

Andrew Howroyd, Jan 17 2022

nonn

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

Row 4 of A350820.

Cf. A193768 (domination number).

a(n) = a(n-3) + 2*a(n-4) + a(n-7) for n > 16.

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A375566 Array read by antidiagonals: T(m,n) = number of minimum dominating sets in the stacked prism graph C_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A350821 Number of minimum dominating sets in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A350822 Number of minimum dominating sets in the grid graph P_4 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula