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.