A133515 -id:A133515 - cp's OEIS frontend

A218354 T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.

1, 3, 3, 5, 11, 5, 9, 41, 41, 9, 17, 149, 291, 149, 17, 31, 547, 2069, 2069, 547, 31, 57, 2007, 14811, 28661, 14811, 2007, 57, 105, 7361, 105913, 401253, 401253, 105913, 7361, 105, 193, 27001, 757305, 5609569, 10982565, 5609569, 757305, 27001, 193, 355

Offset: 1

R. H. Hardin, Oct 26 2012

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

			Table starts
....1.......3...........5..............9.................17
....3......11..........41............149................547
....5......41.........291...........2069..............14811
....9.....149........2069..........28661.............401253
...17.....547.......14811.........401253...........10982565
...31....2007......105913........5609569..........300126903
...57....7361......757305.......78394141.........8199377227
..105...27001.....5415209.....1095695529.......224032447213
..193...99043....38722037....15314367301......6121258910011
..355..363299...276885777...214044940145....167250519310183
..653.1332617..1979899795..2991651891557...4569773233045519
.1201.4888173.14157473937.41813576818545.124859601874166153
...
Some solutions for n=3 k=4
..1..0..1..1....1..1..1..0....1..1..1..0....1..0..1..1....1..0..1..1
..1..0..1..0....1..0..1..0....0..0..1..0....1..0..1..1....1..1..0..1
..0..0..1..0....1..1..0..1....0..1..1..1....1..1..1..1....1..1..1..0

Stephan Mertens, Table of n, a(n) for n = 1..946 (first 198 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.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Dominating Set
Wikipedia, Dominating Set

Columns 1-7 are A000213(n+1), A218348, A218349, A218350, A218351, A218352, A218353.
Diagonal is A133515.
Cf. A089934 (independent vertex sets), A210662 (matchings).

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) +2*a(n-2) +2*a(n-3) -a(n-4) -a(n-5).
k=3: a(n) = 6*a(n-1) +5*a(n-2) +22*a(n-3) +7*a(n-4) +8*a(n-5) -18*a(n-6) -20*a(n-7) -a(n-8) +4*a(n-9) +3*a(n-10) +a(n-12).
Column k=1 for an underlying 0..z array: a(n) = sum(i=1..2z+1){a(n-i)} z=1,2,3,4

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

Original entry on oeis.org

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

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

Original entry on oeis.org

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

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

A197048 Number of n X n 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Original entry on oeis.org

1, 2, 10, 42, 358, 4468, 88056, 2745186, 134355866, 10264692132, 1234801357470, 232966546265096, 68939282741912248

Offset: 1

R. H. Hardin, Oct 09 2011

nonn

Every 0 is next to 0 0's, every 1 is next to 1 0's, every 2 is next to 2 0's, every 3 is next to 3 0's, every 4 is next to 4 0's.

Also, the number of maximal independent vertex sets in the grid graph P_n X P_n. - Andrew Howroyd, May 16 2017

			Some solutions for n=4
..0..2..0..2....2..0..1..1....2..0..3..0....0..3..0..2....1..0..3..0
..1..1..2..0....0..3..1..0....0..4..0..2....3..0..3..0....1..2..0..3
..2..0..2..1....3..0..2..1....3..0..2..1....0..2..1..1....0..1..3..0
..0..3..0..1....0..3..0..1....0..2..1..0....1..1..0..1....1..1..0..2

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

Diagonal of A197054.

Cf. A006506 (independent vertex sets), A133515 (dominating sets).

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

A347632 Number of minimum dominating sets in the n X n grid graph.

Original entry on oeis.org

1, 6, 10, 2, 22, 288, 2, 52, 32, 4, 32, 21600, 18, 540360, 34528, 100406, 70266144, 1380216154, 1682689266, 77900162, 233645826, 200997249200

Offset: 1

Eric W. Weisstein, Sep 09 2021

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

Main diagonal of A350820.

Cf. A104519 (domination number), A133515 (dominating sets), A290382 (minimal dominating sets).

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

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

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.

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

Original entry on oeis.org

1, 6, 4, 1, 10, 57, 98, 80, 36, 9, 1, 2, 40, 554, 2484, 5494, 7268, 6402, 3964, 1760, 556, 120, 16, 1, 22, 1545, 22594, 140304, 492506, 1126091, 1823057, 2204694, 2063202, 1528544, 908623, 435832, 168426, 51953, 12550, 2296, 300, 25, 1, 288, 20896, 478624

Offset: 1

Eric W. Weisstein, Nov 25 2024

Sum_{k=A104519(n+2)..n^2} T(n,k) = A133515(n).

T(n,n^2) = 1.

			D_1(x)=x
D_2(x)=6*x^2+4*x^3+x^4
D_3(x)=10*x^3+57*x^4+98*x^5+80*x^6+36*x^7+9*x^8+x^9
D_4(x)=2*x^4+40*x^5+554*x^6+2484*x^7+5494*x^8+7268*x^9+6402*x^10+3964*x^11+1760*x^12+556*x^13+120*x^14+16*x^15+x^16

Eric W. Weisstein, Table of n, a(n) for n = 1..2922
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, Domatic Number.
Eric Weisstein's World of Mathematics, Dominating Set.
Eric Weisstein's World of Mathematics, Domination Number.
Eric Weisstein's World of Mathematics, Grid Graph.

Cf. A104519 (domination number of the (n-2) X (n-2) grid graph).
Cf. A133515 (number of dominating sets in the n X n grid graph).
Cf. A000290 (vertex count of the n X n grid graph = n^2).

cp's OEIS Frontend

A218354 T(n,k) = Hilltop maps: number of nXk binary arrays indicating the locations of corresponding elements not exceeded by any horizontal or vertical neighbor in a random 0..1 n X k array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

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

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A197048 Number of n X n 0..4 arrays with each element equal to the number of its horizontal and vertical zero neighbors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A347632 Number of minimum dominating sets in the n X n grid 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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs