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

**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:

- {CF90} F. Comellas and M.A. Fiol,
Vertex symmetric digraphs with small diameter.,
*Discrete Applied Mathematics*, vol. 58 (1995), pp. 1-12. - {D91} M.J. Dinneen,
Algebraic methods for efficient network constructions,
*Master Thesis*, University of Victoria, 1991.

If your browser does not support tables, please click here to load an ascii version of the table.

Related problems are the so called (,D)