PDF

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

UPPER BOUNDS FOR THE DOMINATION NUMBERS OF TOROIDAL QUEENS GRAPHS

Christina M. Mynhardt

Department of Mathematics
University of South Africa
P.O. Box 392 Unisa 0003 South Africa
e-mail: mynhacm@unisa.ac.za

Abstract

We determine upper bounds for γ(Q_n^t) and i(Q_n^t), the domination and independent domination numbers, respectively, of the graph Q_n^t 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.

References

[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