Distance in Graphs.

 Distance in Graphs :

Recall:

The distance between two vertices u & v of a graph G, denoted by

 d(u,v), is the length of any u-v Geodeisc in G .

( Length of a shortest path from u to v ),

( If no path exist between u & v , then d(u,v) = Infinity )

Ex:

d(u₁, u₆) = 3 , d(u₄, u₆) = 2

d(u₃, u₆) = 1 , d(u₁, u₇) = Infinity

Definition :

Let G be a graph & v is a vertex of G. 

Then eccentricity of v, denoted by e(v), is the maximum distance between v and all 

other vertex of G, i.e

e(v) = max d(u,v) , u belongs to the vertices in G

Ex:

e(b) = 3 , e(a) = 4 , e(t) = 2 ,---

Definition :

We call a vertex , w, an eccentric vertex of v if d(v,w) = e(v) .

In Ex:

k is an eccentric vertex of b k , a and f are eccentric vertices of t

Definition:

(1) The minimum eccentricity among the vertices of a graph G is called the raduis of G, written rad(G) .

(2) The set of vertices with minimum eccentricity is called the center of G, denoted by C(G).

(3) The periphery of a graph G, denoted P(G) , is the set of vertices of G with maximum eccentricity .

(4) The maximum eccentricity among all vertices if a graph G is called

 the diameter of G , denoted by diam(G).

Ex:

Consider the following graph , the eccentricity of each vertex is given .

Observe that

Rad(G) = 4 .

C(G) = {r, c}.

diam(G) = 7 .

P(G) = {i, p, q}.

Remark: If G is disconnected, then diam(G) = Infinity .

Remark:

(1) If G is a graph & u,v & w are vertices of G , then

d(u,v) <= d(u,w) + d(u,w)

( Triangle Inequality )

(2) If G is a graph & u & v are two adjacent vertices of G , then

|e(u) – e(v)| <= 1

Theorem : Let G be a graph then

rad(G) <= diam(G) <= 2rad(G) .

Proof : It is obvious that rad(G) <= diam(G) .

Let v₁ , v₂ be two vertices of G such that d(v₁ , v₂) = diam(G) .

Let u be any vertex of C(G) .

Then using triangle inequality diam(G) = d(v₁ , v₂ ) <= d(v₁ ,u) + d(v₂ , u)

Since u Belong to C(G), then d(v₁ ,u) <= rad(G) & d(v₂ , u) <= rad(G) .

Thus diam(G) <= rad(G) + rad(G)

diam(G) <= 2 rad(G).