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 C5. 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.