Distance-Defined Subgraphs

In a connected graph G, there is a path connecting every two vertices of G; in fact, there may be several such paths. For vertices u and v of G, the length of a shortest u- v path in G is the distance between u and v. For every vertex v of G, it is often of interest to know the distance from v to a vertex of G farthest from v (the eccentricity of v). The total distance of v is the sum of the distances from v to all vertices of G. The vertices of a connected graph having minimum eccentricity, those having maximum eccentricity, and those having minimum total distance and the subgraphs induced by these three sets of vertices are the primary topics of this chapter.