OFFSET
0,13
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.
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.
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).
EXAMPLE
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.
PROG
(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))}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, May 20 2025
STATUS
approved