login
A299029
Triangle read by rows: Independent domination number for rectangular queens graph Q(n,m), 1 <= n <= m.
3
1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 4, 1, 2, 3, 3, 4, 4, 4, 1, 2, 3, 4, 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, 7, 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
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 an independent dominating set of Q(n X m) is the independent domination number, denoted by i(Q(n X m)).
Less formally, i(Q(n X m)) is the number of independent queens that are necessary and sufficient to all squares of the n X m chessboard be occupied or attacked.
Chessboards 8 X 11 and 18 X 11 are of special interest, because they cannot be dominated by 5 and 8 independent queens, respectively, although the larger boards 9 X 11, 10 X 11, 11 X 11 and 18 X 12 are. It is open how many such counterexamples of this kind of monotonicity exist.
LINKS
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queens graph, arXiv:1606.02060 [math.CO], 2016.
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queens graph, 2016.
Eric Weisstein's World of Mathematics, Queen Graph
Eric Weisstein's World of Mathematics, Queens Problem
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 3
5 | 1 2 2 3 3
6 | 1 2 2 3 3 4
7 | 1 2 3 3 4 4 4
8 | 1 2 3 4 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 7
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 7 7 7 7 8 8 9 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 9 8 9 9 9 10 10 10
CROSSREFS
Diagonal elements are in A075324: Independent domination number for queens graph Q(n).
Cf. A274138: Domination number for rectangular queens graph Q(n,m).
Cf. A279404: Independent domination number for queens graph on an n X n toroidal board.
Sequence in context: A097028 A289442 A092331 * A200747 A328481 A089293
KEYWORD
nonn,tabl
AUTHOR
Sandor Bozoki, Feb 01 2018
STATUS
approved