An improved upper bound for queens domination numbers
type: Item
instance of: scholarly article
title: An improved upper bound for queens domination numbers
zbMATH Open document ID: 1015.05066
DOI: 10.1016/S0012-365X(02)00802-6
published in: Discrete Mathematics
publication date: 2003-06-09T00:00:00Z
review text: 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 \textit{W. D. Weakley} [Discrete Math. 242, 229-243 (2002; Zbl 0988.05069)]. A similar result is also obtained for the toroidal queen's graph.
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1924760
zbMATH Keywords: chessboard
zbMATH Keywords: dominating set
zbMATH Keywords: queen's graph
zbMATH Keywords: toroidal chessboard
author: A. P. Burger
author: Christina M. Mynhardt
reviewed by: Patric R. J. Östergård
MaRDI profile type: Publication
cites work: Q4309111
cites work: Domination and irredundance in the queens' graph
cites work: Queens graphs for chessboards on the torus
cites work: Q4500610
cites work: Q4503111
cites work: An upper bound for the minimum number of queens covering the \(n {\times} n\) chessboard
cites work: Chessboard domination problems
cites work: Q4349621
cites work: Q4368728
cites work: Computational methods and new results for chessboard problems
cites work: Upper bounds for the domination numbers of toroidal queens graphs
cites work: Values of domination numbers of the queen's graph
cites work: Q4871084
cites work: Upper bounds for domination numbers of the queen's graph
cites work: Q4798534
full work available at URL: s0012-365x(02)00802-6
OpenAlex ID: W2166530698
description: scientific article; zbMATH DE number 1924760