ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 23(1) (2003) 163-175
DOI: 10.7151/dmgt.1193


Christina M. Mynhardt

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


We determine upper bounds for γ(Qnt) and i(Qnt), the domination and independent domination numbers, respectively, of the graph Qnt obtained from the moves of queens on the n×n chessboard drawn on the torus.

Keywords: queens graph, toroidal chessboards, queens domination problem.

2000 Mathematics Subject Classification: 05C69.


[1] W. Ahrens, Mathematische Unterhalten und Spiele (B.G. Teubner, Leipzig-Berlin, 1910).
[2] M. Bezzel, Schachfreund, Berliner Schachzeitung, 3 (1848) 363.
[3] A.P. Burger, E.J. Cockayne and C.M. Mynhardt, Queens graphs for chessboards on the torus, Australas. J. Combin. 24 (2001) 231-246.
[4] A.P. Burger and C.M. Mynhardt, Symmetry and domination in queens graphs, Bulletin of the ICA 29 (2000) 11-24.
[5] A.P. Burger and C.M. Mynhardt, Properties of dominating sets of the queens graph Q4k+3, Utilitas Math. 57 (2000) 237-253.
[6] A.P. Burger and C.M. Mynhardt, An improved upper bound for queens domination numbers, Discrete Math., to appear.
[7] 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.
[8] E.J. Cockayne, Chessboard Domination Problems, Discrete Math. 86 (1990) 13-20, doi: 10.1016/0012-365X(90)90344-H.
[9] C.F. de Jaenisch, Applications de l'Analyse Mathematique au Jeu des Echecs (Petrograd, 1862).
[10] S.M. Hedetniemi, S.T. Hedetniemi and R. Reynolds, Combinatorial problems on chessboards: II. in: T.W. Haynes, S.T. Hedetniemi and P.J. Slater, eds, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
[11] M.D. Kearse and P.B. Gibbons, Computational methods and new results for chessboard problems, Australas. J. Combin. 23 (2001) 253-284.
[12] P. Monsky, Problem E3162, Amer. Math. Monthly 96 (1989) 258-259, doi: 10.2307/2325220.
[13] 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.
[14] 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).
[15] W.D. Weakley, A lower bound for domination numbers of the queen's graph, J. Combin. Math. Combin. Comput., to appear.
[16] 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.

Received 2 October 2001
Revised 18 January 2002