×

An improved upper bound for queens domination numbers. (English) Zbl 1015.05066

The queen’s graph \(Q_n\) has the squares of the \(n \times n\) chessboard as its vertices; two vertices are adjacent if the corresponding squares are in the same row, column, or diagonal. The minimum size of a dominating set of \(Q_n\) is denoted by \(\gamma(Q_n)\).
The authors show that if, for some fixed \(k\), there is a dominating set of \(Q_{4k+1}\) of a certain type with cardinality \(2k+1\), then for any \(n\) large enough, \(\gamma(Q_n)\leq n(3k+5)/(6k+3)+O(1)\), improving slightly on the results of W. D. Weakley [Discrete Math. 242, 229-243 (2002; Zbl 0988.05069)]. A similar result is also obtained for the toroidal queen’s graph.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 0988.05069
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M., Domination numbers for the queen’s graph, Bull. Inst. Combin. Appl., 10, 73-82 (1994) · Zbl 0805.05042
[2] Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M., Domination and irredundance in the queen’s graph, Discrete Math., 163, 47-66 (1997) · Zbl 0873.05055
[3] Burger, A. P.; Cockayne, E. J.; Mynhardt, C. M., Queens graphs for chessboards on the torus, Australas. J. Combin., 24, 231-246 (2001) · Zbl 0979.05080
[4] Burger, A. P.; Mynhardt, C. M., Symmetry and domination in queens graphs, Bull. Inst. Combin. Appl., 29, 11-24 (2000) · Zbl 0954.05034
[5] Burger, A. P.; Mynhardt, C. M., Properties of dominating sets of the queens graph \(Q_{4k+3}\), Utilitas Math., 57, 237-253 (2000) · Zbl 0955.05076
[6] Burger, A. P.; Mynhardt, C. M., An upper bound for the minimum number of queens covering the \(n\)×\(n\) chessboard, Discrete Appl. Math., 121, 51-60 (2002) · Zbl 0993.05105
[7] Burger, A. P.; Mynhardt, C. M.; Weakley, W. D., Queens graphs for chessboards on the torus, Australas. J. Combin., 24, 231-246 (2001) · Zbl 0979.05080
[8] Cockayne, E. J., Chessboard domination problems, Discrete Math., 86, 13-20 (1990) · Zbl 0818.05057
[9] C.F. de Jaenisch, Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd, 1862.; C.F. de Jaenisch, Applications de l’Analyse Mathematique au Jeu des Echecs. Petrograd, 1862.
[10] Gibbons, P. B.; Webb, J. A., Some new results for the queens domination problem, Austral. J. Combin., 15, 145-160 (1997) · Zbl 0880.05023
[11] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel-Dekker: Marcel-Dekker New York · Zbl 0890.05002
[12] Kearse, M. D.; Gibbons, P. B., Computational methods and new results for chessboard problems, Austral. J. Combin., 23, 253-284 (2001) · Zbl 0966.05053
[13] C.M. Mynhardt, Upper bounds for the domination number of toroidal Queens graphs, Discussiones Math. 23 (2003), to appear.; C.M. Mynhardt, Upper bounds for the domination number of toroidal Queens graphs, Discussiones Math. 23 (2003), to appear. · Zbl 1035.05066
[14] P.R.J. Östergård, W.D. Weakley, Values of domination numbers of the queen’s graph, preprint.; P.R.J. Östergård, W.D. Weakley, Values of domination numbers of the queen’s graph, preprint. · Zbl 0973.05058
[15] W.D. Weakley, Domination in the queen’s graph, in: Y. Alavi, A.J. Schwenk, (Eds.), Graph Theory, Combinatorics, and Algorithms, Vol. 2, Wiley-Interscience, New York, 1995, pp. 1223-1232.; W.D. Weakley, Domination in the queen’s graph, in: Y. Alavi, A.J. Schwenk, (Eds.), Graph Theory, Combinatorics, and Algorithms, Vol. 2, Wiley-Interscience, New York, 1995, pp. 1223-1232. · Zbl 0842.05053
[16] Weakley, W. D., Upper bounds for domination numbers of the queen’s graph, Discrete Math., 242, 229-243 (2002) · Zbl 0988.05069
[17] W.D. Weakley, A lower bound for domination numbers of the queen’s graph, J. Combin. Math. Combin. Comput., to appear.; W.D. Weakley, A lower bound for domination numbers of the queen’s graph, J. Combin. Math. Combin. Comput., to appear. · Zbl 1012.05124
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.