Repository logo
 

Aspects of distance and domination in graphs.

dc.contributor.advisorSwart, Hendrika Cornelia Scott.
dc.contributor.advisorDankelmann, Peter A.
dc.contributor.authorSmithdorf, Vivienne.
dc.date.accessioned2012-03-22T08:03:27Z
dc.date.available2012-03-22T08:03:27Z
dc.date.created1995
dc.date.issued1995
dc.descriptionThesis (Ph.D.-Mathematics and Applied Mathematics)-University of Natal, 1995.en
dc.description.abstractThe 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.en
dc.identifier.urihttp://hdl.handle.net/10413/5142
dc.language.isoenen
dc.subjectTheses--Mathematics.en
dc.subjectGraph theory.en
dc.titleAspects of distance and domination in graphs.en
dc.typeThesisen

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Smithdorf_V_1995.pdf
Size:
4.62 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.64 KB
Format:
Item-specific license agreed upon to submission
Description: