A292073 -id:A292073 - cp's OEIS frontend

A292074 Number of minimum dominating sets in the n X n rook complement graph.

1, 4, 48, 240, 1000, 3300, 9114, 21952, 47520, 94500, 175450, 307824, 515112, 828100, 1286250, 1939200, 2848384, 4088772, 5750730, 7942000, 10789800, 14443044, 19074682, 24884160, 32100000, 40982500, 51826554, 64964592, 80769640, 99658500, 122095050

Offset: 1

Eric W. Weisstein, Sep 12 2017

The minimum dominating sets are the minimal dominating sets (A291623) of size equal to the domination number. For n > 2, the domination number is 3. For n > 3, the minimal dominating sets of size 3 are either any three vertices such that no two are in the same row or column or any vertex with another in the same row and a third in the same column. For n = 3, the case of all vertices in a single row or column also needs to be included. - Andrew Howroyd, Sep 13 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Rook Complement Graph
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A291623, A292073.

Join[{1, 4, 48}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {240, 1000, 3300, 9114, 21952, 47520, 94500}, 20]]
Table[Piecewise[{{1, n == 1}, {48, n == 3}}, 6 Binomial[n, 3]^2 + n^2 (n - 1)^2], {n, 20}]
CoefficientList[Series[(-1 + 3 x - 41 x^2 + 47 x^3 - 223 x^4 + 221 x^5 - 217 x^6 + 127 x^7 - 42 x^8 + 6 x^9)/(-1 + x)^7, {x, 0, 20}], x]

a(n) = if(n<4, [1,4,48][n], 6*binomial(n, 3)^2 + n^2*(n-1)^2); \\ Andrew Howroyd, Sep 13 2017

G.f.: x*(-1 + 3*x - 41*x^2 + 47*x^3 - 223*x^4 + 221*x^5 - 217*x^6 + 127*x^7 - 42*x^8 + 6*x^9)/(-1 + x)^7.
a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 10.
a(n) = 6*binomial(n, 3)^2 + n^2*(n-1)^2 for n > 3. - Andrew Howroyd, Sep 13 2017

Terms a(6) and beyond from Andrew Howroyd, Sep 13 2017

A384121 Array read by antidiagonals: T(n,m) is the number of dominating sets in the n X m rook complement graph.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 39, 39, 1, 1, 1, 1, 183, 421, 183, 1, 1, 1, 1, 833, 3825, 3825, 833, 1, 1, 1, 1, 3629, 32047, 64727, 32047, 3629, 1, 1, 1, 1, 15291, 260355, 1046425, 1046425, 260355, 15291, 1, 1, 1, 1, 63051, 2092909, 16771879, 33548731, 16771879, 2092909, 63051, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

Non-dominating sets are just those that are contained in the union of a single row and column minus the intersecting vertex.

			Array begins:
===============================================================
n\m | 0 1     2       3         4           5             6 ...
----+----------------------------------------------------------
  0 | 1 1     1       1         1           1             1 ...
  1 | 1 1     1       1         1           1             1 ...
  2 | 1 1     9      39       183         833          3629 ...
  3 | 1 1    39     421      3825       32047        260355 ...
  4 | 1 1   183    3825     64727     1046425      16771879 ...
  5 | 1 1   833   32047   1046425    33548731    1073727713 ...
  6 | 1 1  3629  260355  16771879  1073727713   68719441881 ...
  7 | 1 1 15291 2092909 268422785 34359704907 4398046428559 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Eric Weisstein's World of Mathematics, Dominating Set.
Eric Weisstein's World of Mathematics, Rook Complement Graph.

Main diagonal is A292073.
Columns 0 and 1 are A000012.
Column 2 is A287063, n > 1.
Cf. A384120 (independent sets), A384122, A384123.

T(n,m) = if(n<=1 || m<=1, 1, 2^(n*m) - n*(2^m-2) - m*(2^n-2) + n*m - n*m*(2^(m-1)-1)*(2^(n-1)-1) + n*(n-1)*m*(m-1)/2 - 1)

T(n,m) = 2^(n*m) - n*(2^m-2) - m*(2^n-2) + n*m - n*m*(2^(m-1)-1)*(2^(n-1)-1) + n*(n-1)*m*(m-1)/2 - 1 for n > 1, m > 1.

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

A303209 Number of total dominating sets in the n X n rook complement graph.

Original entry on oeis.org

0, 1, 334, 63935, 33543096, 68719407273, 562949953031502, 18446744073707484655, 2417851639229258338871776, 1267650600228229401496650964865, 2658455991569831745807614120307390270, 22300745198530623141535718272648360299110799

Offset: 1

Eric W. Weisstein, Apr 19 2018

nonn

The vertex sets which are not totally dominating are just those that are contained in the union of a single row and column. - Andrew Howroyd, Apr 20 2018

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

Cf. A292073, A303212, A347922.

a(n) = {2^(n^2) - 2*n*(2^n - 1) - 2*n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2/2 + n^2 - 1} \\ Andrew Howroyd, Apr 20 2018

a(n) = 2^(n^2) - 2*n*(2^n - 1) - 2*n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2/2 + n^2 - 1. - Andrew Howroyd, Apr 20 2018

Terms a(6) and beyond from Andrew Howroyd, Apr 20 2018

A290949 Number of connected dominating sets in the n X n rook complement graph.

Original entry on oeis.org

1, 0, 325, 63899, 33542996, 68719407048, 562949953031061, 18446744073707483871, 2417851639229258338870480, 1267650600228229401496650962840, 2658455991569831745807614120307387245, 22300745198530623141535718272648360299106443

Offset: 1

Eric W. Weisstein, Sep 14 2017

nonn

Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Rook Complement Graph

Cf. A291593, A292073.

Table[If[n == 1, 1, 2^(n^2) - 2 n (2^n - 1) + n^2 (1 - 2 (2^(n - 1) - 1)^2 + (n - 1)^2) - 3 Binomial[n, 2]^2 - 1], {n, 20}] (* Eric W. Weisstein, Jan 15 2018 *)

a(n) = if(n==1, 1, 2^(n^2) - 2*n*(2^n - 1) + n^2 - 2*n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 3*binomial(n,2)^2 - 1); \\ Andrew Howroyd, Jan 14 2018

a(n) = 2^(n^2) - 2*n*(2^n - 1) + n^2 - 2*n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 3*binomial(n,2)^2 - 1 for n > 1. - Andrew Howroyd, Jan 14 2018

a(6)-a(12) from Andrew Howroyd, Jan 14 2018

cp's OEIS Frontend

A292074 Number of minimum dominating sets in the n X n rook complement graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A384121 Array read by antidiagonals: T(n,m) is the number of dominating sets in the n X m rook complement graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A303209 Number of total dominating sets in the n X n rook complement graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A290949 Number of connected dominating sets in the n X n rook complement graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions