On The Queen Domination Problem

Document Type


Publication Date


Published In

Discrete Mathematics


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.