Thesis (MSc)--University of Stellenbosch, 2004. / ENGLISH ABSTRACT: Motivation for the study of protection strategies for graphs is rooted in antiquity and has
evolved as a subdiscipline of graph theory since the early 1990s. Using, as a point of departure,
the notions of weak Roman domination and secure domination (where protection of a graph is
required against a single attack) an initial framework for higher order domination was introduced
in 2002 (allowing for the protection of a graph against an arbitrary finite, or even infinite, number
of attacks). In this thesis, the theory of higher order domination in graphs is broadened yet
further to include the possibility of an arbitrary number of guards being stationed at a vertex.
The thesis firstly provides a comprehensive survey of the combinatorial literature on Roman
domination, weak Roman domination, secure domination and other higher order domination
strategies, with a view to summarise the state of the art in the theory of higher order graph
domination as at the start of 2004.
Secondly, a generalised framework for higher order domination is introduced in two parts: the
first catering for the protection of a graph against a finite number of consecutive attacks, and the
second concerning the perpetual security of a graph (protection of the graph against an infinite
number of consecutive attacks). Two types of higher order domination are distinguished: smart
domination (requiring the existence of a protection strategy for any sequence of consecutive
attacks of a pre–specified length, but leaving it up to a strategist to uncover such a guard
movement strategy for a particular instance of the attack sequence), and foolproof domination
(requiring that any possible guard movement strategy be a successful protection strategy for the
graph in question). Properties of these higher order domination parameters are examined—first
by investigating the application of known higher order domination results from the literature,
and secondly by obtaining new results, thereby hopefully improving current understanding of
these domination parameters.
Thirdly, the thesis contributes by (i) establishing higher order domination parameter values
for some special graph classes not previously considered (such as complete multipartite graphs,
wheels, caterpillars and spiders), by (ii) summarising parameter values for special graph classes
previously established (such as those for paths, cycles and selected cartesian products), and by
(iii) improving higher order domination parameter bounds previously obtained (in the case of
the cartesian product of two cycles).
Finally, a clear indication of unresolved problems in higher order graph domination is provided
in the conclusion to this thesis, together with some suggestions as to possibly desirable future
generalisations of the theory. / AFRIKAANSE OPSOMMING: Die motivering vir die studie van verdedigingstrategie¨e vir grafieke het sy ontstaan in die antieke
wˆereld en het sedert die vroe¨e 1990s as ’n subdissipline in grafiekteorie begin ontwikkel. Deur
gebruik te maak van die idee van swak Romynse dominasie en versterkte dominasie (waar
verdediging van ’n grafiek teen ’n enkele aanval vereis word) het ’n aanvangsraamwerk vir ho¨er–
orde dominasie (wat ’n grafiek teen ’n veelvuldige, of selfs oneindige aantal, aanvalle verdedig)
in 2002 die lig gesien. Die teorie van ho¨er–orde dominasie in grafieke word in hierdie tesis
verbreed, deur toe te laat dat ’n arbitrˆere aantal wagte by elke punt van die grafiek gestasioneer
mag word.
Eerstens voorsien die tesis ’n omvangryke oorsig van die kombinatoriese literatuur oor Romynse
dominasie, swak Romynse dominasie, versterkte dominasie en ander ho¨er–orde dominasie strategie
¨e, met die doel om die kundigheid betreffende die teorie van ho¨er–orde dominasie, soos aan
die begin van 2004, op te som.
Tweedens word ’n veralgemeende raamwerk vir ho¨er–orde dominasie bekendgestel, en wel in
twee dele. Die eerste deel maak voorsiening vir die verdediging van ’n grafiek teen ’n eindige
aantal opeenvolgende aanvalle, terwyl die tweede deel betrekking het op die oneindige sekuriteit
van ’n grafiek (verdediging teen ’n oneindige aantal opeenvolgende aanvalle). Daar word tussen
twee tipes h¨oer–orde dominasie onderskei: intelligente dominasie (wat slegs die bestaan van
’n verdedigingstrategie vir enige reeks opeenvolgende aanvalle vereis, maar dit aan ’n strateeg
oorlaat om ’n suksesvolle bewegingstrategie vir die verdediging teen ’n spesifieke reeks aanvalle
te vind), en onfeilbare dominasie (wat vereis dat enige moontlike bewegingstrategie resulteer in
’n suksesvolle verdedigingstrategie vir die betrokke grafiek). Eienskappe van hierdie ho¨er–orde
dominasie parameters word ondersoek, deur eerstens die toepasbaarheid van bekende ho¨er–orde
dominasie resultate vanuit die literatuur te assimileer, en tweedens nuwe resultate te bekom,
in die hoop om die huidige kundigheid met betrekking tot hierdie dominasie parameters te
verbreed.
Derdens word ’n bydrae gelewer deur (i) ho¨er–orde dominasie parameterwaardes vas te stel
vir sommige spesiale klasse grafieke wat nie voorheen ondersoek is nie (soos volledig veelledige
grafieke, wiele, ruspers en spinnekoppe), deur (ii) parameterwaardes wat reeds bepaal is (soos
byvoorbeeld di´e vir paaie, siklusse en sommige kartesiese produkte) op te som, en deur (iii)
bekende ho¨er–orde dominasie parametergrense te verbeter (in die geval van die kartesiese produk
van twee siklusse).
Laastens word ’n aanduiding van oop probleme in die teorie van ho¨er–orde dominasie in die
slothoofstuk van die tesis voorsien, tesame met voorstelle ten opsigte van moontlik sinvolle
veralgemenings van die teorie.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/16257 |
| Date | 12 1900 |
| Creators | Benecke, Stephen |
| Contributors | Van Vuuren, J.H., Grobler, P.J.P., University of Stellenbosch. Faculty of Science. Dept. of Mathematical Sciences. |
| Publisher | Stellenbosch : University of Stellenbosch |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | xxiv, 145 leaves : ill. |
| Rights | University of Stellenbosch |
Page generated in 0.015 seconds