In this thesis we investigate how the modification of a graph affects various
distance measures. The questions considered arise in the study of how the
efficiency of communications networks is affected by the loss of links or nodes.
In a graph C, the distance between two vertices is the length of a shortest
path between them. The eccentricity of a vertex v is the maximum distance
from v to any vertex in C. The radius of C is the minimum eccentricity of a
vertex, and the diameter of C is the maximum eccentricity of a vertex. The
distance of C is defined as the sum of the distances between all unordered
pairs of vertices.
We investigate, for each of the parameters radius, diameter and distance
of a graph C, the effects on the parameter when a vertex or edge is removed or
an edge is added, or C is replaced by a spanning tree in which the parameter is
as low as possible. We find the maximum possible change in the parameter
due to such modifications. In addition, we consider the cases where the
removed vertex or edge is one for which the parameter is minimised after
deletion.
We also investigate graphs which are critical with respect to the radius or
diameter, in any of the following senses: the parameter increases when any
edge is deleted, decreases when any edge is added, increases when any vertex
is removed, or decreases when any vertex is removed. / Thesis (M.Sc.)-University of Natal, 1996.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:ukzn/oai:http://researchspace.ukzn.ac.za:10413/5141 |
| Date | January 1996 |
| Creators | Swart, Christine Scott. |
| Contributors | Swart, Henda C., Goddard, Wayne. |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0019 seconds