In the mathematical subfield of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance.

There are a number of other measurements defined in terms of distance:

The eccentricity $\backslash epsilon$ of a vertex $v$ is the greatest distance between $v$ and any other vertex.

The radius of a graph is the minimum eccentricity of any vertex.

The diameter of a graph is the maximum eccentricity of any vertex in the graph. That is, it is the greatest distance between any two vertices. A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter.

A pseudo-peripheral vertex $v$ has the property that for any vertex $u$, if $v$ is as far away from $u$ as possible, then $u$ is as far away from $v$ as possible. Formally, if the distance from $u$ to $v$ equals the eccentricity of $u$, then it equals the eccentricity of $v$.

Algorithm for finding pseudo-peripheral vertices

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

1. Choose a vertex $u$.
2. Among all the vertices that are as far from $u$ as possible, let $v$ be one with minimal degree.
3. If $\backslash epsilon(v)\; >\; \backslash epsilon(u)$ then set u=v and repeat with step 2, else v is a pseudo-peripheral vertex.

See also

• Betweenness
• Centrality
• Closeness
• Distance matrix

Graph theory