Thesis (PhD)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The domination number of a graph is the cardinality of a smallest subset of its vertex set with
the property that each vertex of the graph is in the subset or adjacent to a vertex in the subset.
This graph parameter has been studied extensively since its introduction during the early 1960s
and finds application in the generic setting where the vertices of the graph denote physical
entities that are typically geographically dispersed and have to be monitored efficiently, while
the graph edges model links between these entities which enable guards, stationed at the vertices,
to monitor adjacent entities.
In the above application, the guards remain stationary at the entities. In 2005, this constraint
was, however, relaxed by the introduction of a new domination-related parameter, called the
secure domination number. In this relaxed, dynamic setting, each unoccupied entity is defended
by a guard stationed at an adjacent entity who can travel along an edge to the unoccupied entity
in order to resolve a security threat that may occur there, after which the resulting configuration
of guards at the entities is again required to be a dominating set of the graph. The secure
domination number of a graph is the smallest number of guards that can be placed on its
vertices so as to satisfy these requirements.
In this generalised setting, the notion of edge removal is important, because one might seek the
cost, in terms of the additional number of guards required, of protecting the complex of entities
modelled by the graph if a number of edges in the graph were to fail (i.e. a number of links
were to be eliminated form the complex, thereby disqualifying guards from moving along such
disabled links).
A comprehensive survey of the literature on secure graph domination is conducted in this dissertation.
Descriptions of related, generalised graph protection parameters are also given. The
classes of graphs with secure domination number 1, 2 or 3 are characterised and a result on
the number of defenders in any minimum secure dominating set of a graph without end-vertices
is presented, after which it is shown that the decision problem associated with computing the
secure domination number of an arbitrary graph is NP-complete.
Two exponential-time algorithms and a binary programming problem formulation are presented
for computing the secure domination number of an arbitrary graph, while a linear algorithm is
put forward for computing the secure domination number of an arbitrary tree. The practical
efficiencies of these algorithms are compared in the context of small graphs.
The smallest and largest increase in the secure domination number of a graph are also considered
when a fixed number of edges are removed from the graph. Two novel cost functions are
introduced for this purpose. General bounds on these two cost functions are established, and
exact values of or tighter bounds on the cost functions are determined for various infinite classes
of special graphs. Threshold information is finally established in respect of the number of possible edge removals
from a graph before increasing its secure domination number. The notions of criticality and
stability are introduced and studied in this respect, focussing on the smallest number of arbitrary
edges whose deletion necessarily increases the secure domination number of the resulting graph,
and the largest number of arbitrary edges whose deletion necessarily does not increase the secure
domination number of the resulting graph. / AFRIKAANSE OPSOMMING: Die dominasiegetal van ’n grafiek is die kardinaalgetal van ’n kleinste deelversameling van die
grafiek se puntversameling met die eienskap dat elke punt van die grafiek in die deelversameling
is of naasliggend is aan ’n punt in die deelversameling. Hierdie grafiekparameter is sedert die
vroeë 1960s uitvoerig bestudeer en vind toepassing in die generiese situasie waar die punte van
die grafiek fisiese entiteite voorstel wat tipies geografies verspreid is en doeltreffend gemonitor
moet word, terwyl die lyne van die grafiek skakels tussen hierdie entiteite voorstel waarlangs
wagte, wat by die entiteite gebaseer is, naasliggende entiteite kan monitor.
In die bogenoemde toepassing, bly die wagte bewegingloos by die fisiese entiteite waar hulle
geplaas word. In 2005 is hierdie beperking egter verslap met die daarstelling van ’n nuwe
dominasie-verwante grafiekparameter, bekend as die sekure dominasiegetal. In hierdie verslapte,
dinamiese situasie word elke punt sonder ’n wag deur ’n wag verdedig wat by ’n naasliggende
punt geplaas is en wat langs die verbindingslyn na die leë punt kan beweeg om daar ’n bedreiging
te neutraliseer, waarna die gevolglike plasing van wagte weer ’n dominasieversameling van die
grafiek moet vorm. Die sekure dominasiegetal van ’n grafiek is die kleinste getal wagte wat op
die punte van die grafiek geplaas kan word om aan hierdie vereistes te voldoen.
Die beginsel van lynverwydering speel ’n belangrike rol in hierdie veralgemeende situasie, omdat
daar gevra mag word na die koste, in terme van die addisionele getal wagte wat vereis word, om
die kompleks van entiteite wat deur die grafiek gemodelleer word, te beveilig indien ’n aantal
lynfalings in die grafiek plaasvind (m.a.w. indien ’n aantal skakels uit die kompleks van entiteite
verwyder word, en wagte dus nie meer langs sulke skakels mag beweeg nie).
’n Omvattende literatuurstudie oor sekure dominasie van grafieke word in hierdie verhandeling
gedoen. Beskrywings van verwante, veralgemeende verdedigingsparameters in grafiekteorie word
ook gegee. Die klasse van grafieke met sekure dominasiegetal 1, 2 of 3 word gekarakteriseer
en ’n resultaat oor die getal verdedigers in enige kleinste sekure dominasieversameling van ’n
grafiek sonder endpunte word daargestel, waarna daar getoon word dat die beslissingsprobleem
onderliggend aan die berekening van die sekure dominasiegetal van ’n arbitrêre grafiek NP-
volledig is.
Twee eksponensiële-tyd algoritmes en ’n binêre programmeringsformulering word vir die bepaling
van die sekure dominasiegetal van ’n arbitrêre grafiek daargestel, terwyl ’n lineêre algoritme vir
die berekening van die sekure dominasiegetal van ’n arbitrêre boom ontwerp word. Die praktiese
doeltreffendhede van hierdie algoritmes word vir klein grafieke met mekaar vergelyk. Die kleinste en groostste toename in die sekure dominasiegetal van ’n grafiek word ook oorweeg
wanneer ’n vaste getal lyne uit die grafiek verwyder word. Twee nuwe kostefunksies word vir
hierdie doel daargestel en algemene grense word op hierdie kostefunksies vir arbitrêre grafieke
bepaal, terwyl eksakte waardes van of verbeterde grense op hierdie kostefunksies vir verskeie
oneindige klasse van spesiale grafieke bereken word.
Drempelinligting word uiteindelik bepaal in terme van die moontlike getal lynverwyderings uit
’n grafiek voordat die sekure dominasiegetal daarvan toeneem. Die konsepte van kritiekheid en
stabiliteit word in hierdie konteks bestudeer, met ’n fokus op die kleinste getal arbitrêre lynfalings
wat noodwendig die sekure dominasiegetal van die gevolglike grafiek laat toeneem, of die grootste
getal arbitrêre lynfalings wat noodwendig die sekure dominasiegetal van die gevolglike grafiek
onveranderd laat.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/95841 |
| Date | 12 1900 |
| Creators | De Villiers, Anton Pierre |
| Contributors | Van Vuuren, Jan Harm, Burger, A. P., Stellenbosch University. Faculty of Engineering. Department of Industrial Engineering. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | Unknown |
| Type | Thesis |
| Format | xxiv, 191 p. : ill. |
| Rights | Stellenbosch University |
Page generated in 0.0037 seconds