Return to search

Aspects of distance and domination in graphs.

The first half of this thesis deals with an aspect of domination; more specifically, we



investigate the vertex integrity of n-distance-domination in a graph, i.e., the extent



to which n-distance-domination properties of a graph are preserved by the deletion



of vertices, as well as the following: Let G be a connected graph of order p and let



oi- S s;:; V(G). An S-n-distance-dominating set in G is a set D s;:; V(G) such that



each vertex in S is n-distance-dominated by a vertex in D. The size of a smallest



S-n-dominating set in G is denoted by I'n(S, G). If S satisfies I'n(S, G) = I'n(G),



then S is called an n-distance-domination-forcing set of G, and the cardinality of a



smallest n-distance-domination-forcing set of G is denoted by On(G). We investigate



the value of On(G) for various graphs G, and we characterize graphs G for which



On(G) achieves its lowest value, namely, I'n(G), and, for n = 1, its highest value,



namely, p(G). A corresponding parameter, 1](G), defined by replacing the concept



of n-distance-domination of vertices (above) by the concept of the covering of edges



is also investigated.



For k E {a, 1, ... ,rad(G)}, the set S is said to be a k-radius-forcing set if, for each



v E V(G), there exists Vi E S with dG(v, Vi) ~ k. The cardinality of a smallest



k-radius-forcing set of G is called the k-radius-forcing number of G and is denoted



by Pk(G). We investigate the value of Prad(G) for various classes of graphs G,



and we characterize graphs G for which Prad(G) and Pk(G) achieve specified values.



We show that the problem of determining Pk(G) is NP-complete, study the



sequences (Po(G),Pl(G),P2(G), ... ,Prad(G)(G)), and we investigate the relationship



between Prad(G)(G) and Prad(G)(G + e), and between Prad(G)(G + e) and the connectivity



of G, for an edge e of the complement of G.



Finally, we characterize integral triples representing realizable values of the triples



b,i,p), b,l't,i), b,l'c,p), b,l't,p) and b,l't,l'c) for a graph. / Thesis (Ph.D.-Mathematics and Applied Mathematics)-University of Natal, 1995.

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:ukzn/oai:http://researchspace.ukzn.ac.za:10413/5142
Date January 1995
CreatorsSmithdorf, Vivienne.
ContributorsSwart, Henda C., Dankelmann, Peter A.
Source SetsSouth African National ETD Portal
LanguageEnglish
Detected LanguageEnglish
TypeThesis

Page generated in 0.0135 seconds