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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A279402 Domination number for queens' graph on an n X n toroidal board. 5

%I

%S 1,1,1,2,3,3,4,4,5,5,5,6,7,7,5

%N Domination number for queens' graph on an n X n toroidal board.

%C That is, the minimal number of queens needed to cover an n X n toroidal chessboard so that every square either has a queen on it, or is under attack by a queen, or both.

%C Row lengths of the triangle A279403.

%C All dominating sets are translation-invariant on the torus.

%C a(4*n) <= 2*n.

%C a(n) <= A075458(n).

%D John J. Watkins, Across the Board: The Mathematics of Chessboard Problem, Princeton University Press, 2004, pages 139-140.

%H A. P. Burger and C. M. Mynhardt, <a href="https://ajc.maths.uq.edu.au/pdf/28/ajc_v28_p137.pdf">The domination number of the toroidal queens graph of size 3k × 3k</a>, Australasian Journal of Combinatorics, 28 (2003), 137-148.

%H Christina M. Mynhardt, <a href="http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1193/c/dmgt.1193.pdf">Upper bounds for the domination numbers of toroidal queens graphs</a>, Discussiones Mathematicae Graph Theory, 23 (2003), 163-175, DOI:10.7151/dmgt.1193.

%F a(3*n) = n if n = 1, 5, 7, 11 (mod 12);

%F a(3*n) = n+1 if n = 2, 10 (mod 12);

%F a(3*n) = n+2 otherwise.

%F I.e., a(3*n) = 2*n - A085801(n).

%e The minimal dominating set for the queens' graph on a 15 X 15 toroidal board is:

%e ...............

%e ..........Q....

%e ...............

%e ...............

%e .Q.............

%e ...............

%e ...............

%e .......Q.......

%e ...............

%e ...............

%e .............Q.

%e ...............

%e ...............

%e ....Q..........

%e ...............

%e Hence a(15) = 5.

%Y Cf. A075458, A274138, A279403-A279409.

%K nonn,hard,more

%O 1,4

%A _Andrey Zabolotskiy_, Dec 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 February 20 06:26 EST 2019. Contains 320332 sequences. (Running on oeis4.)