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

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

Author

Andrew Howroyd, May 20 2025

Keywords

• nonn
• tabl

Comments

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.

Examples

			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.
		

Links

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

Crossrefs

Main diagonal is A291623.

Columns 0 and 1 are A000012.

Column 2 is A289121 for n > 1.

Cf. A384121, A384122.

Programs

PARI

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

Formula

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