Distance measures in graphs and subgraphs.

Abstract

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.