A292074 -id:A292074 - cp's OEIS frontend

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

1, 9, 421, 64727, 33548731, 68719441881, 562949953225997, 18446744073708516927, 2417851639229258344138819, 1267650600228229401496677076985, 2658455991569831745807614120434020301, 22300745198530623141535718272648360902500919

Offset: 1

Eric W. Weisstein, Sep 12 2017

nonn

Non-dominating sets are just those that are contained in the union of a single row and column minus the intersecting vertex. - Andrew Howroyd, Sep 13 2017

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

Cf. A291623, A292074.

[1] cat [2^(n^2)-2*n*(2^n-2)+n^2-n^2*(2^(n-1)-1)^2+ n^2*(n-1)^2-2*Binomial(n,2)^2-1: n in [2..15]]; // Vincenzo Librandi, Mar 17 2018

Table[If[n == 1, 1, 2^n^2 + (2^n (n - 2) - 4^(n - 1) n + (n - 1)^2 n/2 + 4) n - 1], {n, 20}]

a(n) = if(n == 1, 1, 2^(n^2) - 2*n*(2^n - 2) + n^2 - n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 2*binomial(n,2)^2 - 1); \\ Andrew Howroyd, Sep 13 2017

a(n) = 2^(n^2) - 2*n*(2^n - 2) + n^2 - n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 2*binomial(n,2)^2 - 1 for n > 1. - Andrew Howroyd, Sep 13 2017

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

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

Original entry on oeis.org

0, 1, 51, 492, 2500, 8925, 25431, 61936, 134352, 266625, 493075, 861036, 1433796, 2293837, 3546375, 5323200, 7786816, 11134881, 15604947, 21479500, 29091300, 38829021, 51143191, 66552432, 85650000, 109110625, 137697651, 172270476, 213792292, 263338125

Offset: 1

Eric W. Weisstein, Sep 19 2021

From Andrew Howroyd, Jan 19 2022: (Start)
The vertex sets which are not totally dominating are just those that are contained in the union of a single row and column. Minimal total dominating sets are:
  - any three vertices such that no two are in the same row or column,
  - two vertices in each of two rows/columns. (End)

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Minimal Total 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. A292074, A303209, A303212.

Table[(n - 1)^2 n^2 (5 n^2 - 11 n + 5)/12, {n, 20}] (* Eric W. Weisstein, May 11 2024 *)
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 1, 51, 492, 2500, 8925, 25431}, 20] (* Eric W. Weisstein, May 11 2024 *)
CoefficientList[Series[-x (1 + 44 x + 156 x^2 + 92 x^3 + 7 x^4)/(-1 + x)^7, {x, 0, 20}], x] (* Eric W. Weisstein, May 11 2024 *)

a(n) = (5*n^2 - 11*n + 5)*n^2*(n-1)^2/12 \\ Andrew Howroyd, Jan 19 2022

From Andrew Howroyd, Jan 19 2022: (Start)
a(n) = 6*binomial(n,3)^2 + 2*binomial(n,2)^3 - binomial(n,2)^2.
a(n) = (5*n^2 - 11*n + 5)*n^2*(n-1)^2/12.
G.f.: x*(1 + 44*x + 156*x^2 + 92*x^3 + 7*x^4)/(1 - x)^7.
(End)

Terms a(6) and beyond from Andrew Howroyd, Jan 19 2022

A384122 Array read by antidiagonals: T(n,m) is the number of minimum 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, 4, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 4, 48, 4, 1, 1, 1, 1, 5, 100, 100, 5, 1, 1, 1, 1, 6, 185, 240, 185, 6, 1, 1, 1, 1, 7, 306, 480, 480, 306, 7, 1, 1, 1, 1, 8, 469, 840, 1000, 840, 469, 8, 1, 1, 1, 1, 9, 680, 1344, 1800, 1800, 1344, 680, 9, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

For n >= 3, m >= 3, the minimum size of a dominating set is 3.

			Array begins:
===============================================
n\m | 0 1 2   3    4    5    6     7     8 ...
----+------------------------------------------
  0 | 1 1 1   1    1    1    1     1     1 ...
  1 | 1 1 1   1    1    1    1     1     1 ...
  2 | 1 1 4   3    4    5    6     7     8 ...
  3 | 1 1 3  48  100  185  306   469   680 ...
  4 | 1 1 4 100  240  480  840  1344  2016 ...
  5 | 1 1 5 185  480 1000 1800  2940  4480 ...
  6 | 1 1 6 306  840 1800 3300  5460  8400 ...
  7 | 1 1 7 469 1344 2940 5460  9114 14112 ...
  8 | 1 1 8 680 2016 4480 8400 14112 21952 ...
   ...

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

Main diagonal is A292074.
Column 3 is A090197(n-1), n >= 4.
Column 4 is A272871(n), n >= 4.
Cf. A384121, A384123.

T(n,m) = if(n<=2||m<=2, if(n<=1||m<=1, 1, if(n==2,m)+if(m==2,n)), 4*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) + if(n==3,m) + if(m==3,n))

T(n,m) = 4*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) for n >= 4, m >= 4.
T(n,m) = T(m,n).
T(n,0) = T(n,1) = 1.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula