Paired, Total, and Connected Domination on the Queen’s Graph Revisited
- 1 1005 Riverside Ave, Kingsport, USA
Abstract
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 .
- Ahrens, W. (1910) Mathematische unterhaltungen und spiele. B.G. Teubner, Leipzig-Berlin.
- Amirabadi, A. (2005) Values of Total Domination Numbers and Connected Domination Numbers in the Queen’s Graph. Master’s Thesis, Clemson University, Clemson.
- Burchett, P.A. (2006) Paired, Total and Connected Domination on the Queen’s Graph. Congressus Numerantium, 178, 207-222.
- De Jaenisch, C.F. (1862) Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd.
- Watkins, J.J. (2004) Across the Board: The Mathematics of Chessboard Problems. Princeton University Press, Princeton and Oxford. http://dx.doi.org/10.1515/9781400840922
- Haynes, T.W., Hedetniemi, S.T. and Slater, P.J., Eds. (1998) Domination in Graphs: Advanced Topics. Marcel Dekker, New York.
- Burchett, P.A. (2011) On the Border Queens Problem and k-Tuple Domination on the Rook’s Graph. Congressus Numerantium, 209, 179-187.