Higher order domination of graphs
Date
2004-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : University of Stellenbosch
Abstract
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.
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.
Description
Thesis (MSc)--University of Stellenbosch, 2004.
Keywords
Domination (Graph theory), Graph theory, Theses -- Applied mathematics, Dissertations -- Applied mathematics