## Aspects of distance and domination in graphs.

dc.contributor.advisor | Swart, Hendrika Cornelia Scott. | |

dc.contributor.advisor | Dankelmann, Peter A. | |

dc.creator | Smithdorf, Vivienne. | |

dc.date.accessioned | 2012-03-22T08:03:27Z | |

dc.date.available | 2012-03-22T08:03:27Z | |

dc.date.created | 1995 | |

dc.date.issued | 1995 | |

dc.identifier.uri | http://hdl.handle.net/10413/5142 | |

dc.description | Thesis (Ph.D.-Mathematics and Applied Mathematics)-University of Natal, 1995. | en |

dc.description.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. | en |

dc.language.iso | en | en |

dc.subject | Theses--Mathematics. | en |

dc.subject | Graph theory. | en |

dc.title | Aspects of distance and domination in graphs. | en |

dc.type | Thesis | en |