Last updated 16-Dec-2004 !
A directed graph or digraph for short, G=(V,A), consists of a
non empty finite set V of elements called vertices and a set
A of ordered pairs of elements of V called arcs. The
number of vertices N = |G| = |V| is the {\it order} of the digraph.
If (x,y) is an arc of A, it is said that x is adjacent to
y or that y is adjacent from x, and it is usually
written x --> y . The out-degree of a vertex
\delta^+(x) is the number of vertices adjacent from x, the
in-degree of a vertex \delta^-(x) is the number of vertices
adjacent to x. A digraph is regular of degree 
or
-regular if the in-degree and out-degree of all
vertices equal . A digraph is strongly connected if
there is a (directed) path from any vertex to every other.
The distance between two vertices x and y, d(x,y),
is the number of arcs of a shortest path from x to y, and its
maximum value among all pairs of vertices,
D=\max_{x, y \in V}d(x,y), is the diameter of the digraph.
The order of a -regular digraph ( > 1) of diameter
D is easily seen to be bounded by
This value is called the Moore bound, and it is known that,
except for =1 or D=1, there exists no -regular
digraphs with N(\Delta, D) vertices and diameter D
\cite{PZ74,BT80}.
A digraph G is vertex symmetric if its automorphism group
acts transitively on its set of vertices.
A (,D) digraph
is a digraph with maximum degree and diameter at most D.
The optimization problem considered consists of
finding vertex symmetric (, D) digraphs which, for a given
diameter and maximum out-degree, have a number of vertices as close
as possible to the Moore bound.
A well known infinite family of large (,D)-digraphs is
the Kautz digraphs \cite{K68,K69}.
The Kautz digraph K(,D), >= 2, has vertices
labeled with words x_1x_2 ...x_D where x_i belongs to an alphabet of
+1 letters and x_i =|= x_{i+1} for 1 =< i =< D-1. A
vertex x_1x_2 ... x_D is adjacent to the vertices x_2 ... x_Dx_{D+1}, where x_{D+1} can be any letter different from
x_D. Hence, the digraph K(,D) is -regular, has
^{D}+^{D-1} vertices and diameter D.
For D=2 the Kautz digraphs are vertex symmetric.
Vertex symmetric digraphs may be easily constructed from
groups. A Cayley digraph Cay (H,S)
is the digraph generated from
the group H and with generating set S.
Dinneen \cite{D91} used a computer search to find
large vertex symmetric (, D) digraphs based on
linear groups and semi-direct products of cyclic groups.
Faber and Moore \cite{FM88} give a family of large vertex symmetric
digraphs which they call \Gamma_\Delta(D).
These digraphs may be defined as digraphs on alphabets
in the following way (Comellas, Fiol 1990):
The vertices are labeled with different words of length D,
x_1x_2 ... x_D, such that they form a D-permutation
of an alphabet of +1 letters. The adjacencies are given by
x_1x_2...x_D ---->
x_2x_3x_4 ... x_Dx_{D+1}, x_{D+1} =/= x_1, x_2, ... , x_D
x_2x_3x_4 ... x_Dx_1
x_1x_3x_4 ... x_Dx_2
x_1x_2x_4 ... x_Dx_3
...
x_1x_2x_3 ... x_Dx_{D-1}
These digraphs have order (+1)_D=\frac{(\Delta+1)!}{(\Delta-D+1)!},
diameter D and are -regular (\Delta \geq D). These
digraphs are also Hamiltonian \cite{JR92}. Note that
the digraphs \Gamma_\Delta(2) are in fact the Kautz digraphs
K(\Delta,2). In the table of large vertex symmetric (\Delta, D) digraphs,
the digraphs \Gamma_\Delta constitute most of the entries of its lower
triangular part, that is digraphs with \Delta > D, (D < 7).
A digraph is k-reachable if for every pair of
vertices x,y \in V there exists a path of exactly k arcs
from x to y.
See \cite{FAYF85,M70} for more details
about k-reachable digraphs.
As an example, the Kautz digraphs of diameter D are
(D+1)-reachable.
The following table give the state of the art with
respect to the
LARGEST KNOWN (,D)- VERTEX SYMMETRIC DIGRAPHS
as in February 1995. Click the position you wish to know the details: digraph description, Moore bound, author, bibliography...
Send new results to cd@lri.fr (Charles Delorme, Laboratoire de Recherche en Informatique, Orsay, France) and comellas@mat.upc.es (Francesc Comellas, DMAT, keeper of this WWW table).
References:
,D)-Vertex Symmetric Digraphs (Dec. 2004) ,D)
graph
problem and (, D,D, 1)- graph problem . We keep also the corresponding tables: