# Eccentricity, Center, Radius, Diameter

Let
*G* be a graph and *v* be a vertex of *G*.
The *eccentricity* of the vertex *v* is
the maximum distance from *v* to any vertex. That is,
*e(v)=*max*{d(v,w):w* in *V(G)}*.

The
*radius* of *G* is the minimum eccentricity
among the vertices of *G*. Therefore,
*radius(G)=*min*{e(v):v* in *V(G)}*.

The
*diameter* of *G* is the maximum eccentricity
among the vertices of *G*. Thus,
*diameter(G)=*max*{e(v):v* in *V(G)}*.

The *girth* of *G* is the length
of a shortest cycle in *G*.

The
*center* of *G* is the set of vertices of
eccentricity equal to the radius.
Hence, *center(G)={v* in *V(G):e(v)=radius(G)}*.

A tree
*T* has *|center(T)|=1* or *|center(T)|=2*.
If *|center(T)|=1*, the tree is called
*central*.
If *|center(T)|=2*, the tree is called
*bicentral*.
A vertex
transitive graph *G* has
*center(G)=V(G)*.
For any graph *G*,
the diameter is at least the radius
and at most twice the radius.
For a tree *T*,
*diameter(T)=2radius(T)-1*, if *T* is
bicentral, and
*diameter(T)=2radius(T)*, if *T* is
central.

A
*(m,n)-cage* is an *m*-regular graph with girth *n* and, subject to this, with the least possible number of vertices.

**Hoffman-Singleton Theorem.**
Let *G* be a *k*-regular graph, with girth *5* and diameter *2*. Then, *k* is in *{2,3,7,57}*.

For *k=2*, the graph is *C*_{5}. For *k=3*, the graph is the Petersen graph. For *k=7*, the graph is called the Hoffman-Singleton graph. Finding a graph for *k=57* is still open, as far as I know.

Hoffman and Singleton proved more: There is an obvious lower bound on *f(m,n)*, the number of vertices in an *(m,n)*-cage. That is,
*(m-2)f(m,n) >= m(m-1)*^{r}-2* if **n=2r+1**
and
**(m-2)f(m,n) >= 2(m-1)*^{r}-2* if **n=2r.*

If *n >= 6* and *m >= 3* and if equality holds, then *n* is in *{6,8,12}*.

Last modified Februrary 1, 1999, by S.C. Locke.
How to contact me.