login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(nxm) has the squares of the nxm 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(nxm) is a dominating set for Q(nxm) if every square of Q(nxm) is either in D or adjacent to a square in D. The minimum size of a dominating set of Q(nxm) is the domination number, denoted by gamma(Q(nxm)).

Less formally, gamma(Q(nxm)) is the number of queens that are necessary and sufficient to all squares of the nxm chessboard be occupied or attacked.

Chessboard 8x11 is of special interest, because it cannot be dominated by 5 queens, although the larger boards 9x11, 10x11 and 11x11 are. It is conjectured that 8x11 is the only counterexample of this kind of monotonicity.

LINKS

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.

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

Sequence in context: A280534 A129451 A097195 * A179301 A008334 A116858

Adjacent sequences:  A274135 A274136 A274137 * A274139 A274140 A274141

KEYWORD

nonn,tabl

AUTHOR

Sandor Bozoki, Jun 11 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 02:33 EST 2019. Contains 320200 sequences. (Running on oeis4.)