Higher order domination of graphs

[摘要] ENGLISH ABSTRACT: Motivation for the study of protection strategies for graphs is rooted in antiquity and hasevolved 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 isrequired against a single attack) an initial framework for higher order domination was introducedin 2002 (allowing for the protection of a graph against an arbitrary finite, or even infinite, numberof attacks). In this thesis, the theory of higher order domination in graphs is broadened yetfurther 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 Romandomination, weak Roman domination, secure domination and other higher order dominationstrategies, with a view to summarise the state of the art in the theory of higher order graphdomination as at the start of 2004.Secondly, a generalised framework for higher order domination is introduced in two parts: thefirst catering for the protection of a graph against a finite number of consecutive attacks, and thesecond concerning the perpetual security of a graph (protection of the graph against an infinitenumber of consecutive attacks). Two types of higher order domination are distinguished: smartdomination (requiring the existence of a protection strategy for any sequence of consecutiveattacks of a pre–specified length, but leaving it up to a strategist to uncover such a guardmovement 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 thegraph in question). Properties of these higher order domination parameters are examined-firstby investigating the application of known higher order domination results from the literature,and secondly by obtaining new results, thereby hopefully improving current understanding ofthese domination parameters.Thirdly, the thesis contributes by (i) establishing higher order domination parameter valuesfor some special graph classes not previously considered (such as complete multipartite graphs,wheels, caterpillars and spiders), by (ii) summarising parameter values for special graph classespreviously 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 ofthe cartesian product of two cycles).Finally, a clear indication of unresolved problems in higher order graph domination is providedin the conclusion to this thesis, together with some suggestions as to possibly desirable futuregeneralisations of the theory.

[发布机构] Stellenbosch University