Upper bounds for the domination numbers of toroidal queens graphs

ArticleOriginal scientific text

Title

Authors ¹

Department of Mathematics, University of South Africa, P.O. Box 392 Unisa 0003 South Africa

We determine upper bounds for

γ (Q n^{t})

and

i (Q ₙ^{t})

, the domination and independent domination numbers, respectively, of the graph

Q ₙ^{t}

obtained from the moves of queens on the n×n chessboard drawn on the torus.

queens graph, toroidal chessboards, queens domination problem

W. Ahrens, Mathematische Unterhalten und Spiele (B.G. Teubner, Leipzig-Berlin, 1910).
M. Bezzel, Schachfreund, Berliner Schachzeitung, 3 (1848) 363.
A.P. Burger, E.J. Cockayne and C.M. Mynhardt, Queens graphs for chessboards on the torus, Australas. J. Combin. 24 (2001) 231-246.
A.P. Burger and C.M. Mynhardt, Symmetry and domination in queens graphs, Bulletin of the ICA 29 (2000) 11-24.
A.P. Burger and C.M. Mynhardt, Properties of dominating sets of the queens graph $Q {4 k + 3}$ , Utilitas Math. 57 (2000) 237-253.
A.P. Burger and C.M. Mynhardt, An improved upper bound for queens domination numbers, Discrete Math., to appear.
A.P. Burger, C.M. Mynhardt and W.D. Weakley, The domination number of the toroidal queens graph of size 3k × 3k, Australas. J. Combin., to appear.
E.J. Cockayne, Chessboard Domination Problems, Discrete Math. 86 (1990) 13-20, doi: 10.2307/2325220.
P.R.J. Östergå rd and W.D. Weakley, Values of domination numbers of the queen's graph, Electron. J. Combin. 8 (2001) no. 1, Research paper 29, 19 pp.
W.D. Weakley, Domination In The Queen's Graph, in: Y. Alavi and A.J. Schwenk, eds, Graph Theory, Combinatorics, and Algorithms, Volume 2, pages 1223-1232 (Wiley-Interscience, New York, 1995).
W.D. Weakley, A lower bound for domination numbers of the queen's graph, J. Combin. Math. Combin. Comput., to appear.
W.D. Weakley, Upper bounds for domination numbers of the queen's graph, Discrete Math. 242 (2002) 229-243, doi:10.1016/S0012-365X(00)00467-2.