Distance (graph theory)

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

1 Definition
2 Algorithm for finding pseudo-peripheral vertices
3 See also

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 <math>u<math> and <math>v<math> by

<math>\mathrm{d}_G(u,v)<math>

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

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

Diameter

The diameter of the graph is defined as

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

Peripheral vertex

A peripheral vertex for G is a vertex v with

<math>\epsilon(v)=\delta(G)<math>

Pseudo-peripheral vertex

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

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

then

<math>\epsilon(v) = \epsilon(u)<math>

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 <math>\lbrace L_0(v),\ldots,L_{\epsilon(v)}(v)\rbrace<math>
choose a vertex u in <math>L_{\epsilon(v)}<math> with minimal degree
if <math>\epsilon(u) > \epsilon(v)<math> then set v=u and repeat with step 2 else u is a pseudo-peripheral vertex