|
|
A274138
|
|
Triangle read by rows: Domination number for rectangular queens' graph Q(n,m), 1 <= n <= m.
|
|
3
|
|
|
1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 3, 4, 4, 1, 2, 3, 3, 4, 4, 5, 5, 1, 2, 3, 4, 4, 4, 5, 5, 5, 1, 2, 3, 4, 4, 4, 5, 5, 5, 5, 1, 2, 3, 4, 4, 5, 5, 6, 5, 5, 5, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 6, 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 7, 1, 2, 3, 4, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,8
|
|
COMMENTS
|
The queens graph Q(n X m) has the squares of the n X m chessboard as its vertices; two squares are adjacent if they are both in the same row, column, or diagonal of the board. A set D of squares of Q(n X m) is a dominating set for Q(n X m) if every square of Q(n X m) is either in D or adjacent to a square in D. The minimum size of a dominating set of Q(n X m) is the domination number, denoted by gamma(Q(n X m)).
Less formally, gamma(Q(n X m)) is the number of queens that are necessary and sufficient to all squares of the n X m chessboard be occupied or attacked.
Chessboard 8 X 11 is of special interest, because it cannot be dominated by 5 queens, although the larger boards 9 X 11, 10 X 11 and 11 X 11 are. It is conjectured that 8 X 11 is the only counterexample of this kind of monotonicity.
|
|
LINKS
|
|
|
EXAMPLE
|
Table begins
m\n|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
--------------------------------------------------------
1 |1
2 |1 1
3 |1 1 1
4 |1 2 2 2
5 |1 2 2 2 3
6 |1 2 2 3 3 3
7 |1 2 3 3 3 4 4
8 |1 2 3 3 4 4 5 5
9 |1 2 3 4 4 4 5 5 5
10 |1 2 3 4 4 4 5 5 5 5
11 |1 2 3 4 4 5 5 6 5 5 5
12 |1 2 3 4 4 5 5 6 6 6 6 6
13 |1 2 3 4 5 5 6 6 6 7 7 7 7
14 |1 2 3 4 5 6 6 6 6 7 7 8 8 8
15 |1 2 3 4 5 6 6 6 7 7 7 8 8 8 9
16 |1 2 3 4 5 6 6 7 7 7 8 8 8 9 9 9
17 |1 2 3 4 5 6 7 7 7 8 8 8 9 9 9 9 9
18 |1 2 3 4 5 6 7 7 8 8 8 8 9 9 9 9 9 9
|
|
CROSSREFS
|
Diagonal elements are in A075458: Domination number for queens' graph Q(n).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|