## 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

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.

 Identifer oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:ukzn/oai:http://researchspace.ukzn.ac.za:10413/5142 Date January 1995 Creators Smithdorf, Vivienne. Contributors Swart, Henda C., Dankelmann, Peter A. Source Sets South African National ETD Portal Language English Detected Language English Type Thesis

Page generated in 0.0135 seconds