A384122 -id:A384122 - cp's OEIS frontend

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

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

A384123 Array read by antidiagonals: T(n,m) is the number of minimal 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, 5, 5, 1, 1, 1, 1, 12, 48, 12, 1, 1, 1, 1, 37, 121, 121, 37, 1, 1, 1, 1, 98, 278, 320, 278, 98, 1, 1, 1, 1, 219, 579, 729, 729, 579, 219, 1, 1, 1, 1, 430, 1102, 1480, 1610, 1480, 1102, 430, 1, 1, 1, 1, 767, 1943, 2741, 3161, 3161, 2741, 1943, 767, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

For n > 2, m > 2, the minimal dominating sets are:
  - all vertices in any single row or column,
  - any three vertices such that no two are in the same row or column,
  - any vertex with another in the same row and a third in the same column,
  - two vertices in each of two rows/columns and none in the same column/row.
Except for (n,m) = (2,3) or (3,2), also the number of maximal irredundant sets in the n X m rook complement graph. In particular, there are 11 maximal irredundant sets in these two graphs.

			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    5   12   37    98   219   430 ...
  3 | 1 1   5   48  121  278   579  1102  1943 ...
  4 | 1 1  12  121  320  729  1480  2741  4716 ...
  5 | 1 1  37  278  729 1610  3161  5682  9533 ...
  6 | 1 1  98  579 1480 3161  6012 10513 17234 ...
  7 | 1 1 219 1102 2741 5682 10513 17948 28827 ...
  8 | 1 1 430 1943 4716 9533 17234 28827 45488 ...
   ...
The T(2,3) = 5 minimal dominating sets are those that contain all vertices in either a single row or a single column. There are also 6 maximal irredundant sets that are not dominating. These are those that contain one vertex in each of the two rows but not in the same column.

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

Main diagonal is A291623.
Columns 0 and 1 are A000012.
Column 2 is A289121 for n > 1.
Cf. A384121, A384122.

T(n,m) = {if(n<=1||m<=1, 1,  n + m + 6*binomial(n,3)*binomial(m,3) + if(n > 2 && m > 2, n*(n-1)*m*(m-1)) + 6*binomial(n,4)*binomial(m,2) + 6*binomial(n,2)*binomial(m,4))}

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

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

cp's OEIS Frontend

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