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
1, 1, 1, 2, 3, 3, 4, 4, 5, 5, 5, 6, 7, 7, 5 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

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.

Row lengths of the triangle A279403.

All dominating sets are translation-invariant on the torus.

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

a(n) <= A075458(n).

REFERENCES

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

LINKS

Table of n, a(n) for n=1..15.

A. P. Burger and C. M. Mynhardt, The domination number of the toroidal queens graph of size 3k × 3k, Australasian Journal of Combinatorics, 28 (2003), 137-148.

Christina M. Mynhardt, Upper bounds for the domination numbers of toroidal queens graphs, Discussiones Mathematicae Graph Theory, 23 (2003), 163-175, DOI:10.7151/dmgt.1193.

FORMULA

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

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

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

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

EXAMPLE

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

...............

..........Q....

...............

...............

.Q.............

...............

...............

.......Q.......

...............

...............

.............Q.

...............

...............

....Q..........

...............

Hence a(15) = 5.

CROSSREFS

Cf. A075458, A274138, A279403-A279409.

Sequence in context: A070984 A134995 A194243 * A189705 A303601 A031247

Adjacent sequences:  A279399 A279400 A279401 * A279403 A279404 A279405

KEYWORD

nonn,hard,more

AUTHOR

Andrey Zabolotskiy, Dec 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 21 11:39 EDT 2018. Contains 316414 sequences. (Running on oeis4.)