Return to search
## Distance measures in graphs and subgraphs.

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.3708 seconds