Properties of edge-deleted distance stable graphs

The distance from a vertex u to a vertex v in a connected graph G is the le ngth of a shortest U-v path in G. The distance of a vertex v of G is the su m of the distances from v to the vertices of G. For a vertex v in a 2-edge- connected graph G, we define the edge-deleted distance of v as the maximum distance of v in G - e over all edges e of G. A Vertex is an edge-deleted d istance stable vertex if the difference between its edge-deleted distance a nd distance is 1. A 2-edge-connected graph G is an edge-deleted distance st able graph if each vertex of G is an edge-deleted distance stable vertex. I n this paper, we investigate the edge-deleted distance of vertices and desc ribe properties of edge-deleted distance stable graphs. (C) 1999 John Wiley & Sons, Inc.