The eccentricity
of a graph vertex
in a connected graph
is the maximum graph
distance between
and any other vertex
of
. For a disconnected
graph, all vertices are defined to have infinite eccentricity (West 2000, p. 71).
The maximum eccentricity is the graph diameter. The minimum graph eccentricity is called the graph radius.
For a disconnected graph, the Wolfram Language function VertexEccentricity[g,
v] gives the eccentricity of in the connected component
containing
rather than assigning infinite eccentricity. For a number of named graphs, precomputed
eccentricities that use the infinite-value convention for disconnected graphs can
be obtained using GraphData[graph,
"Eccentricities"].
For a finite connected graph with at least two vertices, the average eccentricity and the largest independence number of an open graph neighborhood give a lower bound for the induced bipartite subgraph number.