login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

%I

%S 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,

%T 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,

%U 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

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

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

%C 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.

%C 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.

%H Sandor Bozoki, <a href="/A274138/b274138.txt">Table of n, a(n) for n = 1..170</a>

%H S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, <a href="http://arxiv.org/abs/1606.02060">Domination of the rectangular queen’s graph</a>, arXiv:1606.02060 [math.CO], 2016.

%H S. Bozóki, P. Gál, I. Marosi, W. D. Weakley, <a href="http://www.sztaki.mta.hu/~bozoki/queens/">Domination of the rectangular queen’s graph</a>, 2016.

%e Table begins

%e m\n|1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

%e --------------------------------------------------------

%e 1 |1

%e 2 |1 1

%e 3 |1 1 1

%e 4 |1 2 2 2

%e 5 |1 2 2 2 3

%e 6 |1 2 2 3 3 3

%e 7 |1 2 3 3 3 4 4

%e 8 |1 2 3 3 4 4 5 5

%e 9 |1 2 3 4 4 4 5 5 5

%e 10 |1 2 3 4 4 4 5 5 5 5

%e 11 |1 2 3 4 4 5 5 6 5 5 5

%e 12 |1 2 3 4 4 5 5 6 6 6 6 6

%e 13 |1 2 3 4 5 5 6 6 6 7 7 7 7

%e 14 |1 2 3 4 5 6 6 6 6 7 7 8 8 8

%e 15 |1 2 3 4 5 6 6 6 7 7 7 8 8 8 9

%e 16 |1 2 3 4 5 6 6 7 7 7 8 8 8 9 9 9

%e 17 |1 2 3 4 5 6 7 7 7 8 8 8 9 9 9 9 9

%e 18 |1 2 3 4 5 6 7 7 8 8 8 8 9 9 9 9 9 9

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

%K nonn,tabl

%O 1,8

%A _Sandor Bozoki_, Jun 11 2016

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 July 10 15:45 EDT 2020. Contains 335577 sequences. (Running on oeis4.)