Repository logo
 

Distance measures in graphs and subgraphs.

dc.contributor.advisorSwart, Hendrika Cornelia Scott.
dc.contributor.advisorGoddard, Wayne.
dc.contributor.authorSwart, Christine Scott.
dc.date.accessioned2012-03-22T07:39:48Z
dc.date.available2012-03-22T07:39:48Z
dc.date.created1996
dc.date.issued1996
dc.descriptionThesis (M.Sc.)-University of Natal, 1996.en
dc.description.abstractIn 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.en
dc.identifier.urihttp://hdl.handle.net/10413/5141
dc.language.isoenen
dc.subjectGraph theory.en
dc.subjectTheses--Mathematics.en
dc.titleDistance measures in graphs and subgraphs.en
dc.typeThesisen

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Swart_S_Christine_1996.pdf
Size:
5.15 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: