Institutional Repository

The queen's domination problem

Show simple item record

dc.contributor.advisor Mynhardt, C. M. Burger, Alewyn Petrus en 2015-01-23T04:24:20Z 2015-01-23T04:24:20Z 1998-11 en
dc.identifier.citation Burger, Alewyn Petrus (1998) The queen's domination problem, University of South Africa, Pretoria, <> en
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 D.Phil. (Applied Mathematics) en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account