Institutional Repository

# The queen's domination problem

 dc.contributor.advisor Mynhardt, C. M. dc.contributor.author Burger, Alewyn Petrus en dc.date.accessioned 2015-01-23T04:24:20Z dc.date.available 2015-01-23T04:24:20Z dc.date.issued 1998-11 en dc.identifier.citation Burger, Alewyn Petrus (1998) The queen's domination problem, University of South Africa, Pretoria, en dc.identifier.uri http://hdl.handle.net/10500/16179 dc.description.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 dc.format.extent 1 online resource (ii, 113 leaves) en dc.language.iso en dc.subject Chessboards dc.subject Queens graph dc.subject Queens domination problem dc.subject Domination dc.subject Irredundance dc.subject Hexagonal boards dc.subject.ddc 511.5 en dc.subject.lcsh Domination (Graph theory) en dc.title The queen's domination problem en dc.type Thesis dc.description.department Mathematical Sciences dc.description.degree D.Phil. (Applied Mathematics) en
﻿