The queen's domination problem

Abstract

The queens graph Qn has the squares of then x n chessboard as its vertices; two squares are adjacent if they are in the same row, column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote the minimum size of an independent dominating set of Qn. The main purpose of this thesis is to determine new values for'!'( Qn). We begin by discussing the most important known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known values of 'J'(Qn) and explain how they were determined. We briefly explain how to obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It is often useful to study these small dominating sets to look for patterns and possible generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 ) and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3, thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper bound')' (Qn) :s; 1 8 5n + 0 (1), which is better than known bounds in the literature and in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8 we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6