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 / Mathematical Sciences / D.Phil. (Applied Mathematics)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:uir.unisa.ac.za:10500/16179 |
| Date | 11 1900 |
| Creators | Burger, Alewyn Petrus |
| Contributors | Mynhardt, C. M. |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 1 online resource (ii, 113 leaves) |
Page generated in 0.0018 seconds