On The Queen Domination Problem
Document Type
Article
Publication Date
12-14-1990
Published In
Discrete Mathematics
Abstract
A configuration of queens on an m x m chessboard is said to dominate the board if every square either contains a queen or is attacked by a queen. The configuration is said to be non-attacking if no queen attacks another queen. Let f(m) and g(m) equal the minimum number of queens and the minimum number of non-attacking queens, respectively, needed to dominate an m x m chessboard. We prove that: (1) f(m) less-than-or-equal-to 14/23m + O(1), and (2) g(m) less-than-or-equal-to 2/3m + O(1).These are the best upper bounds known at the present time for these functions.
Recommended Citation
Charles M. Grinstead; Bruce M. Hahne , '90; and David W. Van Stone , '88.
(1990).
"On The Queen Domination Problem".
Discrete Mathematics.
Volume 86,
Issue 1-3.
21-26.
DOI: 10.1016/0012-365X(90)90345-I
https://works.swarthmore.edu/fac-math-stat/60