A350823 -id:A350823 - cp's OEIS frontend

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

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

A193768 The domination number of the 4 X n board.

Original entry on oeis.org

2, 3, 4, 4, 6, 7, 7, 8, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67

Offset: 1

Andrew Buchanan, Tanya Khovanova, Alex Ryba, Aug 06 2011

The domination number of a rectangular grid is the minimal number of X-pentominoes or its fragments that can cover the board.

			You can't cover the 1 by 4 board with an X-pentomino, but you can do it with two of them.

Andrew Buchanan, Tanya Khovanova and Alex Ryba, Saturated Domino Coverings, arXiv:1112.2115 [math.CO], 2011.
M. S. Jacobson and L. F. Kinch, On the domination number of products of graphs:I, Ars Combinatoria, vol 18, 1983, 33-44.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Row 4 of A350823.

Cf. A193764, A193765, A193766, A193767.

LinearRecurrence[{2,-1},{2,3,4,4,6,7,7,8,10,10,11},70] (* Harvey P. Dale, Feb 17 2020 *)

Vec(x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x+2)/(x-1)^2 + O(x^100)) \\ Colin Barker, Oct 05 2014

a(n) = n, except for n = 1, 2, 3, 5, 6 or 9. For the exceptions a(n) = n+1.
a(n) = 4n - A193767(n).
a(n) = 2*a(n-1)-a(n-2) for n>11. - Colin Barker, Oct 05 2014
G.f.: x*(x^10-2*x^9+x^8+x^7-x^6-x^5+2*x^4-x^3-x+2) / (x-1)^2. - Colin Barker, Oct 05 2014

A375603 Array read by antidiagonals: T(m,n) = domination number of the stacked prism graph C_m X P_n.

Original entry on oeis.org

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

Offset: 1

Stephan Mertens, Aug 20 2024

			Table starts:
====================================
m\n |   1   2   3    4    5    6 ...
----|-------------------------------
  1 |   1   1   1    2    2    2 ...
  2 |   1   2   2    3    3    4 ...
  3 |   1   2   3    4    4    5 ...
  4 |   2   2   3    4    5    6 ...
  5 |   2   3   4    6    7    8 ...
  6 |   2   4   5    6    8    9 ...
 ...

Stephan Mertens, Table of n, a(n) for n = 1..325
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, Domination Number.
Eric Weisstein's World of Mathematics, Stacked Prism Graph.

Main diagonal is A375601.

Cf. A286514, A350823, A375566.

A381475 Array read by antidiagonals: T(m,n) is the connected 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, 3, 4, 3, 4, 3, 4, 5, 4, 4, 5, 4, 5, 6, 5, 7, 5, 6, 5, 6, 7, 6, 9, 9, 6, 7, 6, 7, 8, 7, 10, 11, 10, 7, 8, 7, 8, 9, 8, 12, 12, 12, 12, 8, 9, 8, 9, 10, 9, 14, 15, 14, 15, 14, 9, 10, 9, 10, 11, 10, 15, 17, 16, 16, 17, 15, 10, 11, 10

Offset: 1

Andrew Howroyd, Mar 19 2025

			Table begins:
=========================================================
m\n |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
----+----------------------------------------------------
  1 |  1  1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 ...
  2 |  1  2  2  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
  3 |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 ...
  4 |  2  4  4  7  9 10 12 14 15 17 19 20 22 24 25 27 ...
  5 |  3  5  5  9 11 12 15 17 18 21 23 24 27 29 30 33 ...
  6 |  4  6  6 10 12 14 16 18 20 22 24 26 28 30 32 34 ...
  7 |  5  7  7 12 15 16 20 23 24 28 31 32 36 39 40 44 ...
  8 |  6  8  8 14 17 18 23 26 27 32 35 36 41 44 45 50 ...
  9 |  7  9  9 15 18 20 24 27 30 33 36 39 42 45 48 51 ...
  ...

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

Main diagonal is A369692.

Cf. A300358, A350823, A381474.

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

cp's OEIS Frontend

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

A193768 The domination number of the 4 X n board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A375603 Array read by antidiagonals: T(m,n) = domination number of the stacked prism graph C_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula