Edge criticality in secure graph domination

[摘要] ENGLISH ABSTRACT: The domination number of a graph is the cardinality of a smallest subset of its vertex set withthe 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 1960sand finds application in the generic setting where the vertices of the graph denote physicalentities that are typically geographically dispersed and have to be monitored efficiently, whilethe 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 constraintwas, however, relaxed by the introduction of a new domination-related parameter, called thesecure domination number. In this relaxed, dynamic setting, each unoccupied entity is defendedby a guard stationed at an adjacent entity who can travel along an edge to the unoccupied entityin order to resolve a security threat that may occur there, after which the resulting configurationof guards at the entities is again required to be a dominating set of the graph. The securedomination number of a graph is the smallest number of guards that can be placed on itsvertices so as to satisfy these requirements.In this generalised setting, the notion of edge removal is important, because one might seek thecost, in terms of the additional number of guards required, of protecting the complex of entitiesmodelled by the graph if a number of edges in the graph were to fail (i.e. a number of linkswere to be eliminated form the complex, thereby disqualifying guards from moving along suchdisabled 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. Theclasses of graphs with secure domination number 1, 2 or 3 are characterised and a result onthe number of defenders in any minimum secure dominating set of a graph without end-verticesis presented, after which it is shown that the decision problem associated with computing thesecure domination number of an arbitrary graph is NP-complete.Two exponential-time algorithms and a binary programming problem formulation are presentedfor computing the secure domination number of an arbitrary graph, while a linear algorithm isput forward for computing the secure domination number of an arbitrary tree. The practicalefficiencies 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 consideredwhen a fixed number of edges are removed from the graph. Two novel cost functions areintroduced for this purpose. General bounds on these two cost functions are established, andexact values of or tighter bounds on the cost functions are determined for various infinite classesof special graphs.Threshold information is finally established in respect of the number of possible edge removalsfrom a graph before increasing its secure domination number. The notions of criticality andstability are introduced and studied in this respect, focussing on the smallest number of arbitraryedges 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 securedomination number of the resulting graph.

[发布机构] Stellenbosch University