distance (graph theory)

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

\mathrm{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

\epsilon(v):= \max_{u \in V} \mathrm{d}_G(v,u)

Diameter

The diameter of the graph is defined as

\delta(G):= \max_{v \in V} \epsilon_G(v)

Peripheral vertex

A peripheral vertex for G is a vertex v with

\epsilon(v)=\delta(G)

Pseudo-peripheral vertex

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

\mathrm{d}_G(v,u) = \epsilon(u)

then

\epsilon(v) = \epsilon(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.

choose a vertex v in V
create a level structure with root v $\lbrace L_0(v),\ldots,L_{\epsilon(v)}(v)\rbrace$
choose a vertex u in $L_{\epsilon(v)}$ with minimal degree
if $\epsilon(u) > \epsilon(v)$ then set v=u and repeat with step 2 else u is a pseudo-peripheral vertex