A291872 -id:A291872 - cp's OEIS frontend

A287690 Number of connected dominating sets in the n X n grid graph.

1, 9, 129, 5617, 964755, 617429805, 1436456861467, 12128014243816259, 370157141019558632729, 40729998558184127557326187, 16129157077874837008807129310501, 22956060013827748812137293758719842059, 117308080543566432787532732819884994609487361

Offset: 1

Eric W. Weisstein, May 29 2017

nonn

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

Main diagonal of A291872.

Cf. A059525, A133515, A289180.

a(6)-a(13) from Andrew Howroyd, Sep 04 2017

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

Original entry on oeis.org

0, 1, 1, 3, 9, 3, 4, 25, 25, 4, 5, 81, 161, 81, 5, 9, 289, 961, 961, 289, 9, 16, 961, 6235, 11236, 6235, 961, 16, 25, 3249, 39601, 137641, 137641, 39601, 3249, 25, 39, 11025, 251433, 1677025, 3270375, 1677025, 251433, 11025, 39

Offset: 1

Andrew Howroyd, Apr 18 2018

Equivalently, the number of n X m binary matrices with every element adjacent to some 0 horizontally or vertically.

			Table begins:
=======================================================================
m\n|  1    2      3        4          5            6              7
---|-------------------------------------------------------------------
1  |  0    1      3        4          5            9             16 ...
2  |  1    9     25       81        289          961           3249 ...
3  |  3   25    161      961       6235        39601         251433 ...
4  |  4   81    961    11236     137641      1677025       20430400 ...
5  |  5  289   6235   137641    3270375     76405081     1783064069 ...
6  |  9  961  39601  1677025   76405081   3416753209   152598828321 ...
7  | 16 3249 251433 20430400 1783064069 152598828321 13057656650476 ...
...

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

Rows 1..2 are A195971(n-1), A141583(n+1).
Main diagonal is A133793.
Cf. A218354 (dominating sets), A291872 (connected dominating sets).
Cf. A303114 (king graph), A303118 (minimal total dominating sets).

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

Original entry on oeis.org

1, 3, 3, 4, 15, 4, 4, 48, 48, 4, 4, 144, 336, 144, 4, 4, 432, 2192, 2192, 432, 4, 4, 1296, 14544, 29648, 14544, 1296, 4, 4, 3888, 96528, 405648, 405648, 96528, 3888, 4, 4, 11664, 640336, 5568336, 11293568, 5568336, 640336, 11664, 4

Offset: 1

Andrew Howroyd, Sep 04 2017

			Array begins:
======================================================================
m\n| 1    2      3        4          5             6               7
---|------------------------------------------------------------------
1  | 1    3      4        4          4             4               4...
2  | 3   15     48      144        432          1296            3888...
3  | 4   48    336     2192      14544         96528          640336...
4  | 4  144   2192    29648     405648       5568336        76414224...
5  | 4  432  14544   405648   11293568     315156544      8793207424...
6  | 4 1296  96528  5568336  315156544   17784998912   1001953789632...
7  | 4 3888 640336 76414224 8793207424 1001953789632 113637188081536...
...

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

Row 2 is A188825(n) for n > 2.
Main diagonal is A289180.
Cf. A218663, A291872.

A360846 Array read by antidiagonals: T(m,n) is the number of dominating induced trees in the grid graph P_m X P_n.

Original entry on oeis.org

1, 3, 3, 4, 8, 4, 4, 17, 17, 4, 4, 32, 65, 32, 4, 4, 66, 222, 222, 66, 4, 4, 130, 766, 1280, 766, 130, 4, 4, 262, 2685, 7629, 7629, 2685, 262, 4, 4, 522, 9450, 46032, 78981, 46032, 9450, 522, 4, 4, 1046, 33158, 278419, 820308, 820308, 278419, 33158, 1046, 4

Offset: 1

Andrew Howroyd, Feb 23 2023

A dominating induced tree in a graph is an acyclic connected induced subgraph whose vertices are a dominating set.

			Table starts:
=======================================================
m\n| 1   2    3      4       5         6          7 ...
---+---------------------------------------------------
1  | 1   3    4      4       4         4          4 ...
2  | 3   8   17     32      66       130        262 ...
3  | 4  17   65    222     766      2685       9450 ...
4  | 4  32  222   1280    7629     46032     278419 ...
5  | 4  66  766   7629   78981    820308    8520021 ...
6  | 4 130 2685  46032  820308  14605388  259809527 ...
7  | 4 262 9450 278419 8520021 259809527 7904828158 ...
  ...

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

Main diagonal is A360847.
Rows 1..2 are A113311(n-1), A360848.
Cf. A291872 (connected dominating sets), A360202 (induced trees).

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

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

A291706 Number of connected dominating sets in the n-ladder graph.

Original entry on oeis.org

3, 9, 24, 56, 136, 328, 792, 1912, 4616, 11144, 26904, 64952, 156808, 378568, 913944, 2206456, 5326856, 12860168, 31047192, 74954552, 180956296, 436867144, 1054690584, 2546248312, 6147187208, 14840622728, 35828432664, 86497488056, 208823408776, 504144305608

Offset: 1

Eric W. Weisstein, Aug 30 2017

Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Ladder Graph
Index entries for linear recurrences with constant coefficients, signature (2, 1).

Row 2 of A291872.

Table[Piecewise[{{3^n, n == 1 || n == 2}}, 4 LucasL[n - 1, 2]], {n, 20}]
Join[{3, 9}, LinearRecurrence[{2, 1}, {24, 56}, 20]]
CoefficientList[Series[(-3 - 3 x - 3 x^2 + x^3)/(-1 + 2 x + x^2), {x, 0, 20}], x]

a(n) = 4 lucas(n - 1, 2) for n > 2.
a(n) = 2*a(n-1) + a(n-2) for n > 4.
G.f.: (x (-3 - 3 x - 3 x^2 + x^3))/(-1 + 2 x + x^2).

cp's OEIS Frontend

A287690 Number of connected dominating sets in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

A360846 Array read by antidiagonals: T(m,n) is the number of dominating induced trees in the grid graph P_m X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A291706 Number of connected dominating sets in the n-ladder graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula