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

A286849 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the n X m king graph.

Original entry on oeis.org

1, 2, 2, 2, 4, 2, 4, 6, 6, 4, 4, 16, 12, 16, 4, 7, 20, 36, 36, 20, 7, 9, 52, 64, 256, 64, 52, 9, 13, 80, 204, 400, 400, 204, 80, 13, 18, 176, 446, 2704, 971, 2704, 446, 176, 18, 25, 296, 1184, 6400, 6486, 6486, 6400, 1184, 296, 25

Offset: 1

Andrew Howroyd, Aug 01 2017

			Array begins:
===========================================================
m\n|  1   2    3     4      5       6        7         8
---|-------------------------------------------------------
1  |  1   2    2     4      4       7        9        13...
2  |  2   4    6    16     20      52       80       176...
3  |  2   6   12    36     64     204      446      1184...
4  |  4  16   36   256    400    2704     6400     30976...
5  |  4  20   64   400    971    6486    22177    112317...
6  |  7  52  204  2704   6486   85405   351503   3082745...
7  |  9  80  446  6400  22177  351503  1997448  21587536...
8  | 13 176 1184 30976 112317 3082745 21587536 360584008...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set

Rows 1-2 are A253413, A286850.
Main diagonal is A286881.
Cf. A218663 (dominating sets), A245013 (independent), A286870 (irredundant).
Cf. A286847 (grid graph).

A286868 Array read by antidiagonals: T(m,n) = number of irredundant sets in the grid graph P_m X P_n.

Original entry on oeis.org

2, 3, 3, 5, 11, 5, 9, 26, 26, 9, 15, 79, 113, 79, 15, 26, 224, 548, 548, 224, 26, 44, 640, 2513, 4481, 2513, 640, 44, 76, 1828, 11826, 34049, 34049, 11826, 1828, 76, 130, 5225, 55136, 265227, 425926, 265227, 55136, 5225, 130

Offset: 1

Andrew Howroyd, Aug 02 2017

			Array begins:
=============================================================
m\n|  1    2     3       4        5          6           7
---|---------------------------------------------------------
1  |  2    3     5       9       15         26          44...
2  |  3   11    26      79      224        640        1828...
3  |  5   26   113     548     2513      11826       55136...
4  |  9   79   548    4481    34049     265227     2052725...
5  | 15  224  2513   34049   425926    5467052    69724154...
6  | 26  640 11826  265227  5467052  116003176  2441933224...
7  | 44 1828 55136 2052725 69724154 2441933224 84850904785...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Irredundant Set

Row 1 is A286887.
Main diagonal is A286869.
Cf. A286847 (minimal dominating sets).
Cf. A286870 (king graph).

A290379 Number of minimal dominating sets in the n-ladder graph.

Original entry on oeis.org

2, 6, 7, 18, 39, 75, 155, 310, 638, 1295, 2624, 5339, 10853, 22069, 44836, 91134, 185259, 376542, 765331, 1555567, 3161843, 6426646, 13062506, 26550391, 53965428, 109688223, 222948193, 453156469, 921069708, 1872133138, 3805230243, 7734373962, 15720610559

Offset: 1

Eric W. Weisstein, Jul 28 2017

nonn

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

Row 2 of A286847.

Cf. A290336, A290337.

I:=[2,6,7,18,39,75,155,310,638,1295,2624]; [n le 11 select I[n] else Self(n-2)+3*Self(n-3)+4*Self(n-4)+4*Self(n-5)+Self(n-6)+2*Self(n-7)+3*Self(n-8)+5*Self(n-9)+4*Self(n-10)+2*Self(n-11): n in [1..40]]; // Vincenzo Librandi, Aug 04 2017

Table[-RootSum[-2 - 4 # - 5 #^2 - 3 #^3 - 2 #^4 - #^5 - 4 #^6 - 4 #^7 - 3 #^8 - #^9 + #^11 &, 621827501801 #^n - 301456826961 #^(n + 1) + 280366986955 #^(n + 2) - 1253389979482 #^(n + 3) + 843186094854 #^(n + 4) - 87555893434 #^(n + 5) + 236346312907 #^(n + 6) - 504072574383 #^(n + 7) + 231943645265 #^(n + 8) - 618185916584 #^(n + 9) + 290649224768 #^(n + 10) &]/2097121971853, {n, 20}] (* Eric W. Weisstein, Aug 04 2017 *)
LinearRecurrence[{0, 1, 3, 4, 4, 1, 2, 3, 5, 4, 2}, {2, 6, 7, 18, 39, 75, 155, 310, 638, 1295, 2624}, 20] (* Eric W. Weisstein, Aug 04 2017 *)
CoefficientList[Series[((1 + x) (2 + 4 x + x^2 + 5 x^3 + x^4 + 3 x^5 + 5 x^6 + 3 x^7 + 2 x^8 + 2 x^9))/(1 - x^2 - 3 x^3 - 4 x^4 - 4 x^5 - x^6 - 2 x^7 - 3 x^8 - 5 x^9 - 4 x^10 - 2 x^11), {x, 0, 20}], x] (* Eric W. Weisstein, Aug 04 2017 *)

Vec((1+x)*(2+4*x+x^2+5*x^3+x^4+3*x^5+5*x^6+3*x^7+2*x^8+2*x^9)/(1-x^2-3*x^3-4*x^4-4*x^5-x^6-2*x^7-3*x^8-5*x^9-4*x^10-2*x^11)+O(x^40)) \\ Andrew Howroyd, Aug 01 2017

From Andrew Howroyd, Aug 01 2017: (Start)
a(n) = a(n-2) + 3*a(n-3) + 4*a(n-4) + 4*a(n-5) + a(n-6) + 2*a(n-7) + 3*a(n-8) + 5*a(n-9) + 4*a(n-10) + 2*a(n-11) for n > 11.
G.f.: x*(1+x)*(2 + 4*x + x^2 + 5*x^3 + x^4 + 3*x^5 + 5*x^6  + 3*x^7 + 2*x^8 + 2*x^9)/(1 - x^2 - 3*x^3 - 4*x^4 - 4*x^5 - x^6 - 2*x^7- 3*x^8 - 5*x^9 - 4*x^10 - 2*x^11).
(End)

Terms a(9) and beyond from Andrew Howroyd, Aug 01 2017

A290382 Number of minimal dominating sets in the n X n grid graph.

Original entry on oeis.org

1, 6, 16, 306, 6958, 349178, 40307167, 8863408138, 4227470143437, 4108988275187691

Offset: 1

Eric W. Weisstein, Jul 28 2017

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

Main diagonal of A286847.

Cf. A133515 (dominating sets), A286869 (irredundant sets).

a(5)-a(9) from Andrew Howroyd, Jul 31 2017

a(10) from Christian Sievers, Dec 03 2023

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.

A286848 Number of minimal dominating sets in the grid graph P_3 X P_n.

Original entry on oeis.org

2, 7, 16, 53, 154, 436, 1268, 3660, 10610, 30744, 89079, 258251, 748420, 2169219, 6287336, 18222901, 52817261, 153084840, 443698814, 1286012537, 3727362387, 10803344089, 31312289784, 90755170545, 263043739916, 762402920030, 2209739758798, 6404684091893

Offset: 1

Andrew Howroyd, Aug 01 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimal Dominating Set

Row 3 of A286847.

G.f.: x*(2 + 3*x - 2*x^2 - x^3 + 4*x^4 + 10*x^5 - 14*x^6 - 32*x^7 - 29*x^8 - 2*x^9 - 21*x^10 - 140*x^11 - 140*x^12 + 126*x^13 + 80*x^14 + 127*x^15 + 143*x^16 + 695*x^17 + 401*x^18 + 462*x^19 + 582*x^20 - 8*x^21 - 490*x^22 - 660*x^23 - 721*x^24 - 960*x^25 - 714*x^26 - 925*x^27 + 25*x^28 + 206*x^29 + 255*x^30 + 494*x^31 + 155*x^32 + 443*x^33 - 118*x^34 + 80*x^35 - 71*x^36 - 172*x^37 + 78*x^38 - 105*x^39 + 79*x^40 + 7*x^41 - 28*x^42 + 33*x^43 - 7*x^44 - 4*x^45 + 3*x^46 - x^47) / (1 - 2*x - 2*x^2 - 4*x^3 + 8*x^4 - 2*x^5 - 2*x^6 - 23*x^7 + 14*x^8 + 31*x^9 + 31*x^10 - 45*x^11 + 50*x^12 + 83*x^13 + 122*x^14 - 141*x^15 - 54*x^16 - 105*x^17 + 36*x^18 - 85*x^19 - 275*x^20 - 222*x^21 + 63*x^22 + 90*x^23 - 140*x^24 + 253*x^25 + 399*x^26 + 234*x^27 + 190*x^28 - 87*x^29 + 59*x^30 - 219*x^31 - 222*x^32 - 189*x^33 - 270*x^34 + 152*x^35 + 56*x^36 + 123*x^37 + 158*x^38 - 41*x^39 + 75*x^40 - 62*x^41 - 12*x^42 + 21*x^43 - 30*x^44 + 7*x^45 + 4*x^46 - 3*x^47 + x^48) (conjectured). - Colin Barker, Aug 02 2017

a(n) = Sum_{k=1..48} c(k)*a(n-k), where c = (2, 2, 4, -8, 2, 2, 23, -14, -31, -31, 45, -50, -83, -122, 141, 54, 105, -36, 85, 275, 222, -63, -90, 140, -253, -399, -234, -190, 87, -59, 219, 222, 189, 270, -152, -56, -123, -158, 41, -75, 62, 12, -21, 30, -7, -4, 3, -1) (conjectured). - Eric W. Weisstein, Aug 02 2017

A291439 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the grid graph P_m X P_n.

Original entry on oeis.org

1, 2, 2, 2, 6, 2, 4, 9, 9, 4, 6, 18, 32, 18, 6, 8, 54, 103, 103, 54, 8, 13, 99, 383, 590, 383, 99, 13, 17, 216, 1280, 2807, 2807, 1280, 216, 17, 27, 512, 4247, 13138, 21555, 13138, 4247, 512, 27, 40, 1079, 14354, 67564, 150063, 150063, 67564, 14354, 1079, 40

Offset: 1

Andrew Howroyd, Aug 23 2017

			Array begins:
=================================================
m\n|  1   2    3     4       5       6       7
---|---------------------------------------------
1  |  1   2    2     4       6       8      13...
2  |  2   6    9    18      54      99     216...
3  |  2   9   32   103     383    1280    4247...
4  |  4  18  103   590    2807   13138   67564...
5  |  6  54  383  2807   21555  150063 1122252...
6  |  8  99 1280 13138  150063 1598353
7  | 13 216 4247 67564 1122252
...

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Maximal Irredundant Set

Rows 1-2 are A291055, A291100.
Main diagonal is A290790.
Cf. A286847, A286868.

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

A286849 Array read by antidiagonals: T(m,n) = number of minimal dominating sets in the n X m king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

A286868 Array read by antidiagonals: T(m,n) = number of irredundant sets in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A290379 Number of minimal dominating sets in the n-ladder graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A290382 Number of minimal dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

A286848 Number of minimal dominating sets in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A291439 Array read by antidiagonals: T(m,n) = number of maximal irredundant sets in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs