In the mathematical subfield of graph theory we can define a notion of distance between two vertices in a graph.

Definition

Given a graph G:=(V,E) with V the set of vertices and E the set of edges then the distance between two vertices is the number of edges in a shortest path connecting the two vertices. We denote the distance of two vertices u and v by

d_G(u,v)

The vertex set V of a connected graph G thus becomes a metric space. For given ordering of vertices it is common to store distances in a distance matrix D(G)of a graph.

Eccentricity

The eccentricity of a vertex v is

Diameter

The diameter of the graph is defined as

Peripheral vertex

A peripheral vertex for G is a vertex v with

ε(v) = δ(G)

Pseudo-peripheral vertex

A vertex v is called pseudo-peripheral vertex if for any vertex u with

d_G(v,u) = ε(u)

then

ε(v) = ε(u)

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. By constructing level structures for the graph we can easily find such a pseudo-peripheral vertex.

1. choose a vertex v in V
2. create a level structure with root v
3. choose a vertex u in L_ε(v) with minimal degree
4. if ε(u) > ε(v) then set v=u and repeat with step 2 else u is a pseudo-peripheral vertex

See also

• Betweenness
• Centrality
• Closeness