Aspects of distance and domination in graphs.

Abstract

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.