Paired, Total, and Connected Domination on the Queen’s Graph Revisited
Paul A. Burchett*
1005 Riverside Ave, Kingsport, USA.
DOI: 10.4236/ojdm.2016.61001   PDF   HTML   XML   4,997 Downloads   6,053 Views   Citations


The question associated with total domination on the queen’s graph has a long and rich history, first having been posed by Ahrens in 1910 [1]. The question is this: What is the minimum number of queens needed so that every square of an n × n board is attacked? Beginning in 2005 with Amirabadi, Burchett, and Hedetniemi [2] [3], work on this problem, and two other related problems, has seen progress. Bounds have been given for the values of all three domination parameters on the queen’s graph. In this paper, formations of queens are given that provide new bounds for the values of total, paired, and connected domination on the queen’s graph, denoted , , and respectively. For any n × n board size, the new bound of is arrived at, along with the separate bounds of , for with , and , for with .

Share and Cite:

Burchett, P. (2016) Paired, Total, and Connected Domination on the Queen’s Graph Revisited. Open Journal of Discrete Mathematics, 6, 1-6. doi: 10.4236/ojdm.2016.61001.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Ahrens, W. (1910) Mathematische unterhaltungen und spiele. B.G. Teubner, Leipzig-Berlin.
[2] Amirabadi, A. (2005) Values of Total Domination Numbers and Connected Domination Numbers in the Queen’s Graph. Master’s Thesis, Clemson University, Clemson.
[3] Burchett, P.A. (2006) Paired, Total and Connected Domination on the Queen’s Graph. Congressus Numerantium, 178, 207-222.
[4] De Jaenisch, C.F. (1862) Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd.
[5] Watkins, J.J. (2004) Across the Board: The Mathematics of Chessboard Problems. Princeton University Press, Princeton and Oxford.
[6] Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Eds. (1998) Domination in Graphs: Advanced Topics. Marcel Dekker, New York.
[7] Burchett, P.A. (2011) On the Border Queens Problem and k-Tuple Domination on the Rook’s Graph. Congressus Numerantium, 209, 179-187.

Copyright © 2023 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.