The (Degree,Diameter) Problem for Vertex-symmetric Digraphs

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 Delta or Delta-regular if the in-degree and out-degree of all vertices equal Delta. 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 Delta-regular digraph (Delta > 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 Delta=1 or D=1, there exists no Delta-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 (Delta,D) digraph is a digraph with maximum degree Delta and diameter at most D. The optimization problem considered consists of finding vertex symmetric (Delta, 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 (Delta,D)-digraphs is the Kautz digraphs \cite{K68,K69}. The Kautz digraph K(Delta,D), Delta>= 2, has vertices labeled with words x_1x_2 ...x_D where x_i belongs to an alphabet of Delta+1 letters and x_i =|= x_{i+1} for 1 =< i =< D-1. A vertex x_1x_2 ... x_D is adjacent to the Delta vertices x_2 ... x_Dx_{D+1}, where x_{D+1} can be any letter different from x_D. Hence, the digraph K(Delta,D) is Delta-regular, has Delta^{D}+Delta^{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 (Delta, 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 Delta+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 (Delta+1)_D=\frac{(\Delta+1)!}{(\Delta-D+1)!}, diameter D and are Delta-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 (Delta,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:


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


LARGEST KNOWN (Delta,D)-Vertex Symmetric Digraphs (Dec. 2004)
Delta\D 2 3 4 5 6 7 8 9 10 11
2 6 10 20 27 72 144 172 336 504 737
3 12 27 60 165 333 1.152 1.860 4.446 10.849 41.472
4 20 60 168 444 1.260 7.200 14.400 38.134 132.012 648.000
5 30 120 360 1.152 3.582 28.800 86.400 259.200 752.914 5.184.000
6 42 210 840 2.520 7.776 88.200 352.800 1.411.200 5.184.000 27.783.000
7 56 336 1.680 6.720 20.160 225.792 1.128.960 5.644.800 27.783.000 113.799.168
8 72 504 3.024 15.120 60.480 508.032 3.048.192 18.289.152 113.799.168 457.228.800
9 90 720 5.040 30.240 151.200 1.036.800 7.257.600 50.803.200 384.072.192 1.828.915.200
10 110 990 7.920 55.400 332.640 1.960.200 15.681.600 125.452.800 1.119.744.000 6.138.320.000
11 132 1.320 11.880 95.040 665.280 3.991.680 31.152.000 282.268.800 2.910.897.000 18.065.203.200
12 156 1.716 17.160 154.440 1.235.520 8.648.640 58.893.120 588.931.200 6.899.904.000 47.703.427.200
13 182 2.184 24.024 240.240 2.162.160 17.297.280 121.080.960 1.154.305.152 15.159.089.098 115.430.515.200

Related problems are the so called (Delta,D) graph problem and (Delta, D,D, 1)- graph problem . We keep also the corresponding tables: