Sandor Bozoki - cp's OEIS frontend

User: Sandor Bozoki

Sandor Bozoki has authored 2 sequences.

A299029 Triangle read by rows: Independent domination number for rectangular queens graph Q(n,m), 1 <= n <= m.

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

Sandor Bozoki, Feb 01 2018

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.

			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

Sandor Bozoki, First 18 rows of the triangle, formatted as a simple linear sequence n, a(n) for n = 1..171
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

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.

A274138 Triangle read by rows: Domination number for rectangular queens' graph Q(n,m), 1 <= n <= m.

Original entry on oeis.org

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

Offset: 1

Sandor Bozoki, Jun 11 2016

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.

			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

Sandor Bozoki, Table of n, a(n) for n = 1..170
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queen’s graph, arXiv:1606.02060 [math.CO], 2016.
S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, Domination of the rectangular queen’s graph, 2016.

Diagonal elements are in A075458: Domination number for queens' graph Q(n).

cp's OEIS Frontend

User: Sandor Bozoki

A299029 Triangle read by rows: Independent domination number for rectangular queens graph Q(n,m), 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs