A133791 -id:A133791 - cp's OEIS frontend

A218663 T(n,k) = Hilltop maps: number of n X k binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X k array.

1, 3, 3, 5, 15, 5, 9, 57, 57, 9, 17, 225, 417, 225, 17, 31, 891, 3249, 3249, 891, 31, 57, 3519, 25533, 50625, 25533, 3519, 57, 105, 13905, 199489, 793881, 793881, 199489, 13905, 105, 193, 54945, 1560161, 12383361, 24879489, 12383361, 1560161, 54945

Offset: 1

R. H. Hardin, Nov 04 2012

From Andrew Howroyd, May 10 2017: (Start)
Number of n X k binary matrices with every 1 adjacent to some 0 horizontally, vertically, diagonally or antidiagonally.
Number of dominating sets in the n X k king graph. (End)

			Table starts
....1........3...........5...............9.................17
....3.......15..........57.............225................891
....5.......57.........417............3249..............25533
....9......225........3249...........50625.............793881
...17......891.......25533..........793881...........24879489
...31.....3519......199489........12383361..........775176415
...57....13905.....1560161.......193349025........24176619049
..105....54945....12202673......3018953025.......754066017977
..193...217107....95434773.....47135449449.....23517838102321
..355...857871...746388537....735942652641....733484062428443
..653..3389769..5837454753..11490533873361..22876204302519509
.1201.13394241.45654295713.179405691966081.713472099034206097
...
Some solutions for n=3 k=4
..1..1..1..0....1..0..1..1....0..1..0..1....0..1..1..0....1..0..0..0
..0..1..0..0....0..0..0..0....1..0..0..1....0..0..1..1....0..0..1..1
..0..1..0..1....1..1..0..1....0..1..1..1....1..1..0..1....1..1..0..0

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 240 terms from R. H. Hardin)
Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
Wikipedia, Dominating set

Columns 1-7 are A000213(n+1), A218657, A218658, A218659, A218660, A218661, A218662.
Diagonal is A133791.
Cf. A218354, A221446, A219078, A218426.

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-3)
k=2: a(n) = 3*a(n-1) +3*a(n-2) +3*a(n-3)
k=3: a(n) = 6*a(n-1) +11*a(n-2) +26*a(n-3) -5*a(n-4) -5*a(n-6)
k=4: a(n) = 12*a(n-1) +45*a(n-2) +180*a(n-3) -27*a(n-4) -81*a(n-6)
Columns k=1..z+1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){(2^k-1)*a(n-i)} checked for z=1..3.

A289180 Number of connected dominating sets in the n X n king graph.

Original entry on oeis.org

1, 15, 336, 29648, 11293568, 17784998912, 113637188081536, 2924018436019899392, 301641905727809350974464, 124378420721322865523465096192, 204571358406088229163099037060664832, 1340178778197906145868721021815647098466816

Offset: 1

Eric W. Weisstein, Jun 27 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, King Graph

Main diagonal of A291873.

Cf. A133791, A286139, A287690.

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

A303116 Number of total dominating sets in the n X n king graph.

Original entry on oeis.org

0, 11, 353, 35458, 16322279, 30158547693, 217221533288240, 6223220939472363571, 709791800918008570287847, 321673400252458591521699180612, 579292884621843116328602359172702605, 4146239141804826663870561644604700888044071

Offset: 1

Andrew Howroyd, Apr 18 2018

nonn

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

Main diagonal of A303114.

Cf. A133791, A302401, A303156, A332391.

A347554 Number of minimum dominating sets in the n X n king graph.

Original entry on oeis.org

1, 4, 1, 256, 79, 1, 243856, 3600, 1, 581571283, 281585, 1, 2722291223553, 32581328, 1, 21706368614058886, 5112264019, 1, 268740319616196074546, 1028516654620, 1, 4839916638142874877046813

Offset: 1

Eric W. Weisstein, Sep 06 2021

a(3*n) = 1 for all n, since the 3n X 3n king graph has domination number n^2 and the only way to achieve this is if each of the n^2 kings is placed in the middle of its own 3 X 3 square.

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
Eric W. Weisstein, Unique minimum dominating set on a 3n X 3n king graph

Main diagonal of A350815.

Cf. A075561 (domination number of the n X n king graph), A133791, A286881.

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

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

A286881 Number of minimal dominating sets in the n X n king graph.

Original entry on oeis.org

1, 4, 12, 256, 971, 85405, 1997448, 360584008, 34097946429, 16133593980207, 8445394800836595, 9548578220258420637

Offset: 1

Eric W. Weisstein, Aug 02 2017

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

Main diagonal of A286849.
Cf. A133791 (dominating sets), A286871 (irredundant sets).
Cf. A290382 (grid graph).

a(5)-a(9) from Andrew Howroyd, Aug 03 2017

a(10)-a(12) from Christian Sievers, Dec 01 2023

A133556 Number of n X n binary matrices with every 1 diagonally or antidiagonally adjacent to some 0.

Original entry on oeis.org

1, 9, 187, 11881, 3720993, 4652194849, 21048197450115, 362982575751004609, 24187438805159042241345, 6154694340999818634869088969, 5974124007380479364088559506443355

Offset: 1

R. H. Hardin, Dec 25 2007

nonn

Number of dominating sets in the direct product of the graphs P_n and P_n. - Andrew Howroyd, May 10 2017

Wikipedia, Tensor product of graphs, Dominating set

Cf. A133515, A133791.

A175563 Number of n X n binary matrices that contain no 2 X 2 zero submatrix.

Original entry on oeis.org

1, 2, 15, 334, 18521, 2293896, 586774783, 292184148320, 270280183791969, 447043237292379520, 1280479639717884356831, 6180626271969237488205312

Offset: 0

Max Alekseyev, Jul 03 2010

Cf. A175564, A133791, A300749.

E.g.f.: the diagonal of exp( Sum_B x^|lB| * y^|rB| / |Aut(B,lB,rB)| ), where B runs over connected squarefree bipartite graphs with ordered bipartitions, (lB,rB) is the bipartition of B, and Aut(B,lB,rB) is the group of automorphisms of B preserving its bipartition.

a(6)-a(8) from Hiroaki Yamanouchi, Aug 27 2014

a(9)-a(11) from Max Alekseyev, Feb 26 2022

A288956 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n king graph.

Original entry on oeis.org

1, 4, 8, 79, 544, 8197, 201611, 6214593, 391918650, 32239887128, 4599025630995, 1018245217588836, 346578151637999287, 193445218205732588935, 165199496607694525364163, 226636538088997406396236072, 488063150616514603623041818756, 1655950305544572458601638523072809

Offset: 1

Eric W. Weisstein, Jun 20 2017

nonn

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

Main diagonal of A332347.

Cf. A197048 (grid graph), A063443 (independent sets), A193580, A133791 (dominating sets).

a(9)-a(18) from Andrew Howroyd, Jun 26 2017

A378420 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n king graph (n>=1, A075561(n)<=k<=n^2).

Original entry on oeis.org

1, 4, 6, 4, 1, 1, 10, 48, 106, 122, 84, 36, 9, 1, 256, 1536, 4480, 8320, 10896, 10560, 7744, 4320, 1816, 560, 120, 16, 1, 79, 1593, 14672, 81524, 307244, 842506, 1764068, 2918828, 3909834, 4311034, 3955232, 3038092, 1957940, 1056965, 475304, 176256, 53046, 12646

Offset: 1

Eric W. Weisstein, Nov 25 2024

Sum_{k=A075561(n)..n^2} T(n,k) = A133791(n).

T(n,n^2) = 1.

			D(1)=x
D(2)=4*x+6*x^2+4*x^3+x^4
D(3)=x+10*x^2+48*x^3+106*x^4+122*x^5+84*x^6+36*x^7+9*x^8+x^9
D(4)=256*x^4+1536*x^5+4480*x^6+8320*x^7+10896*x^8+10560*x^9+7744*x^10+4320*x^11+1816*x^12+560*x^13+120*x^14+16*x^15+x^16

Eric W. Weisstein, Table of n, a(n) for n = 1..3333
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, Domination Number.
Eric Weisstein's World of Mathematics, Domination Polynomial.
Eric Weisstein's World of Mathematics, King Graph.

Cf. A075561 (domination number of the n X n king graph).
Cf. A133791 (number of dominating sets in the n X n king graph).
Cf. A000290 (vertex count of the n X n king graph = n^2).

cp's OEIS Frontend

A218663 T(n,k) = Hilltop maps: number of n X k binary arrays indicating the locations of corresponding elements not exceeded by any king-move neighbor in a random 0..1 n X k array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A289180 Number of connected dominating sets in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A303116 Number of total dominating sets in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

A347554 Number of minimum dominating sets in the n X n king graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A286881 Number of minimal dominating sets in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A133556 Number of n X n binary matrices with every 1 diagonally or antidiagonally adjacent to some 0.

Views

Author

Keywords

Comments

Links

Crossrefs

A175563 Number of n X n binary matrices that contain no 2 X 2 zero submatrix.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A288956 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A378420 Irregular triangle read by rows: T(n,k) is the coefficient of x^k in the domination polynomial of the n X n king graph (n>=1, A075561(n)<=k<=n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs