A218663 -id:A218663 - cp's OEIS frontend

A133791 Number of n X n binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.

1, 15, 417, 50625, 24879489, 48231228511, 373654052856545, 11546079143118274625, 1422756868491071266637985, 699232611373976058162941025423, 1370556061582419558173913152072112161, 10714096395475651010921722651799661109404545

Offset: 1

R. H. Hardin, Jan 05 2008

nonn

Number of dominating sets in the n X n king graph. - Andrew Howroyd, May 10 2017

Stephan Mertens, Table of n, a(n) for n = 1..22 (first 18 terms from Christian Sievers)
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, Dominating Set
Eric Weisstein's World of Mathematics, King Graph
Wikipedia, Dominating set

Main diagonal of A218663.

Cf. A133515, A133556, A063443 (independent vertex sets).

A218663 = Import["https://oeis.org/A218663/b218663.txt", "Table"][[All, 2]];
a[n_] := A218663[[2 n^2 - 2 n + 1]];
Table[a[n], {n, 1, 11}] (* Jean-François Alcover, Sep 23 2019 *)

a(12) and beyond from Christian Sievers, Dec 03 2023

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

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 4, 2, 2, 4, 3, 16, 1, 16, 3, 1, 12, 4, 4, 12, 1, 8, 4, 3, 256, 3, 4, 8, 4, 64, 1, 144, 144, 1, 64, 4, 1, 32, 8, 16, 79, 16, 8, 32, 1, 13, 8, 4, 4096, 9, 9, 4096, 4, 8, 13, 5, 208, 1, 1024, 1656, 1, 1656, 1024, 1, 208, 5, 1, 80, 13, 64, 408, 64, 64, 408, 64, 13, 80, 1

Offset: 1

Andrew Howroyd, Jan 17 2022

The minimum size of a dominating set is the domination number which in the case of an m X n king graph is given by (ceiling(m/3) * ceiling(n/3)).

			Table begins:
============================================
m\n | 1  2  3    4    5   6      7     8
----+---------------------------------------
  1 | 1  2  1    4    3   1      8     4 ...
  2 | 2  4  2   16   12   4     64    32 ...
  3 | 1  2  1    4    3   1      8     4 ...
  4 | 4 16  4  256  144  16   4096  1024 ...
  5 | 3 12  3  144   79   9   1656   408 ...
  6 | 1  4  1   16    9   1     64    16 ...
  7 | 8 64  8 4096 1656  64 243856 29744 ...
  8 | 4 32  4 1024  408  16  29744  3600 ...
     ...

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

Rows 1..3 are A347633, A350816, A347633.
Main diagonal is A347554.
Cf. A075561, A218663 (dominating sets), A286849 (minimal dominating sets), A303335, A350818, A350819.

T(n,m) = T(m,n).
T(3*m, 3*n) = 1; T(3*m+1, 3*n) = (m^2 + 5*m + 2)^n; T(3*m+2, 3*n) = (m+2)^n.
T(3*m-1, 3*n-1) = A350819(m, n).

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

Original entry on oeis.org

2, 3, 3, 5, 5, 5, 9, 11, 11, 9, 15, 25, 43, 25, 15, 26, 51, 133, 133, 51, 26, 44, 113, 463, 647, 463, 113, 44, 76, 235, 1493, 2945, 2945, 1493, 235, 76, 130, 521, 5011, 14217, 22049, 14217, 5011, 521, 130, 223, 1107, 16659, 65627, 147672, 147672, 65627, 16659, 1107, 223

Offset: 1

Andrew Howroyd, Aug 02 2017

			Array begins:
====================================================================
m\n|  1   2     3      4       5         6          7           8
---|----------------------------------------------------------------
1  |  2   3     5      9      15        26         44          76...
2  |  3   5    11     25      51       113        235         521...
3  |  5  11    43    133     463      1493       5011       16659...
4  |  9  25   133    647    2945     14217      65627      322163...
5  | 15  51   463   2945   22049    147672    1043127     7365740...
6  | 26 113  1493  14217  147672   1455385   14656628   151865727...
7  | 44 235  5011  65627 1043127  14656628  218691097  3287831848...
8  | 76 521 16659 322163 7365740 151865727 3287831848 72877697369...
...

Andrew Howroyd, Table of n, a(n) for n = 1..153
Matthew D. Kearse and Peter B. Gibbons, Computational Methods and New Results for Chessboard Problems, CDMTCS Research Reports CDMTCS-133 (2000).
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Irredundant Set

Row 1 is A286887.
Main diagonal is A286871.
Cf. A218663 (dominating sets), A286849 (minimal dominating sets).
Cf. A286868 (grid graph).

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

Original entry on oeis.org

0, 1, 1, 3, 11, 3, 4, 47, 47, 4, 5, 165, 353, 165, 5, 9, 625, 2545, 2545, 625, 9, 16, 2435, 19651, 35458, 19651, 2435, 16, 25, 9367, 150719, 538977, 538977, 150719, 9367, 25, 39, 35901, 1149593, 8213971, 16322279, 8213971, 1149593, 35901, 39

Offset: 1

Andrew Howroyd, Apr 18 2018

			Table begins:
============================================================================
m\n|  1    2       3         4           5             6               7
---|------------------------------------------------------------------------
1  |  0    1       3         4           5             9              16 ...
2  |  1   11      47       165         625          2435            9367 ...
3  |  3   47     353      2545       19651        150719         1149593 ...
4  |  4  165    2545     35458      538977       8213971       124153394 ...
5  |  5  625   19651    538977    16322279     496873689     14980146565 ...
6  |  9 2435  150719   8213971   496873689   30158547693   1812834702647 ...
7  | 16 9367 1149593 124153394 14980146565 1812834702647 217221533288240 ...
...

Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Total Dominating Set

Rows 1..2 are A195971(n-1), A219079.
Main diagonal is A303116.
Cf. A218663 (dominating sets), A291873 (connected dominating sets).
Cf. A303111 (grid graph).

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

Original entry on oeis.org

1, 2, 2, 2, 4, 2, 3, 6, 6, 3, 4, 12, 8, 12, 4, 5, 20, 22, 22, 20, 5, 7, 36, 40, 79, 40, 36, 7, 9, 64, 82, 194, 194, 82, 64, 9, 12, 112, 176, 537, 544, 537, 176, 112, 12, 16, 200, 340, 1519, 1882, 1882, 1519, 340, 200, 16, 21, 352, 722, 4011, 6490, 8197, 6490, 4011, 722, 352, 21

Offset: 1

Andrew Howroyd, Feb 10 2020

Also the number of minimal vertex covers in the m X n king graph.

			Array begins:
=====================================================
m\n | 1   2   3    4     5      6       7       8
----+------------------------------------------------
  1 | 1   2   2    3     4      5       7       9 ...
  2 | 2   4   6   12    20     36      64     112 ...
  3 | 2   6   8   22    40     82     176     340 ...
  4 | 3  12  22   79   194    537    1519    4011 ...
  5 | 4  20  40  194   544   1882    6490   20534 ...
  6 | 5  36  82  537  1882   8197   36301  144409 ...
  7 | 7  64 176 1519  6490  36301  201611 1009321 ...
  8 | 9 112 340 4011 20534 144409 1009321 6214593 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Rows 1..4 are A000931(n+6), A107383(n+2), A332348, A332349.
Main diagonal is A288956.
Cf. A197054 (grid graph), A218663 (dominating sets), A245013 (independent sets), A286849 (minimal dominating sets).

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

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.

A218657 Hilltop maps: number of n X 2 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 2 array.

Original entry on oeis.org

3, 15, 57, 225, 891, 3519, 13905, 54945, 217107, 857871, 3389769, 13394241, 52925643, 209128959, 826346529, 3265203393, 12902036643, 50980759695, 201443999193, 795980386593, 3145215436443, 12427919466687, 49107345869169

Offset: 1

R. H. Hardin, Nov 04 2012

nonn

Column 2 of A218663.

			Some solutions for n=3:
..1..1....1..1....1..0....0..0....1..1....0..1....0..1....0..0....1..1....0..0
..1..1....1..0....1..1....0..1....0..1....0..0....1..0....1..0....0..1....0..1
..1..1....0..1....1..1....0..0....0..1....1..0....0..1....1..1....0..0....0..1

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A218663.

Empirical: a(n) = 3*a(n-1) + 3*a(n-2) + 3*a(n-3).

Empirical g.f.: 3*x*(1 + x)^2 / (1 - 3*x - 3*x^2 - 3*x^3). - Colin Barker, Mar 10 2018

A218658 Hilltop maps: number of n X 3 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 3 array.

Original entry on oeis.org

5, 57, 417, 3249, 25533, 199489, 1560161, 12202673, 95434773, 746388537, 5837454753, 45654295713, 357058903853, 2792531543489, 21840184444225, 170810481722657, 1335896257560101, 10447946710663673, 81712625405191841

Offset: 1

R. H. Hardin, Nov 04 2012

nonn

Column 3 of A218663.

			Some solutions for n=3:
..0..0..1....1..1..0....1..0..0....1..1..0....1..0..0....0..1..0....1..1..1
..1..1..1....1..1..1....0..0..1....1..0..0....1..0..1....0..1..1....0..1..0
..1..0..0....1..1..0....0..1..0....0..1..1....0..1..0....0..1..0....1..1..1

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A218663.

Empirical: a(n) = 6*a(n-1) + 11*a(n-2) + 26*a(n-3) - 5*a(n-4) - 5*a(n-6).

Empirical g.f.: x*(5 + 27*x + 20*x^2 - 10*x^3 - 5*x^4 - 5*x^5) / (1 - 6*x - 11*x^2 - 26*x^3 + 5*x^4 + 5*x^6). - Colin Barker, Mar 10 2018

A218659 Hilltop maps: number of n X 4 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 4 array.

Original entry on oeis.org

9, 225, 3249, 50625, 793881, 12383361, 193349025, 3018953025, 47135449449, 735942652641, 11490533873361, 179405691966081, 2801123686963449, 43734921492423681, 682848585990347841, 10661553197658712449

Offset: 1

R. H. Hardin, Nov 04 2012

nonn

Column 4 of A218663.

			Some solutions for n=3:
..0..1..0..1....1..0..1..0....0..0..0..0....1..0..0..0....1..1..1..1
..0..1..0..1....1..1..0..0....0..1..0..1....1..0..1..0....1..0..0..1
..0..0..0..1....0..0..0..1....0..1..1..1....0..1..1..1....0..1..1..0

R. H. Hardin, Table of n, a(n) for n = 1..210

Cf. A218663.

Empirical: a(n) = 12*a(n-1) +45*a(n-2) +180*a(n-3) -27*a(n-4) -81*a(n-6).

Empirical g.f.: 9*x*(1 - x)*(1 + 14*x + 30*x^2 + 18*x^3 + 9*x^4) / ((1 + 3*x + 9*x^2 - 9*x^3)*(1 - 15*x - 9*x^2 - 9*x^3)). - Colin Barker, Mar 10 2018

cp's OEIS Frontend

A133791 Number of n X n binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

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

A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A218657 Hilltop maps: number of n X 2 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 2 array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A218658 Hilltop maps: number of n X 3 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 3 array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A218659 Hilltop maps: number of n X 4 binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X 4 array.

Views

Author

Keywords

Comments