Largest Known (Degree, Diameter)-Vertex Symmetric Digraphs

Under Construction !

KAUTZ DIGRAPHS.


All the entries in the table for diameter 2 correspond to Kautz digraphs.


A well known infinite family of large (Delta,D)-digraphs is the Kautz digraphs. See references.
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.

References
[15]W.H.Kautz, Bounds on directed (d,k) graphs.Theory of cellular login networks and machines, AFCRL-68-0668, SRI Project 7258, Final Report, pp.20-28,1968.
[16]W.H.Kautz, Design of optimal interconnection networks for multiprocessors. Architecture and Design of Digital Computers, Nato Advanced Summer Institute,pp.249-272,1969.

CYCLE PREFIX DIGRAPHS.


Faber and Moore give a family of large vertex symmetric digraphs which they denote Gamma_Gamma(D) and call cycle prefix digraphs. 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 (Gamma+1)! / (Gamma+1-D)!, diameter D and are Delta-regular (Gamma > D).
These digraphs are also Hamiltonian. Note that the digraphs Gamma_Gamma(2) are in fact the Kautz digraphs K(Gamma,2). In the table of large vertex symmetric (Gamma, D) digraphs, the digraphs Gamma_Gamma(D) constitute most of the entries of its lower triangular part, that is digraphs with Gamma > D, (D < 8).

Delta\D 3 4 5 6 7 8
4 60
5 120 360
6 210 840 2.520
7 336 1.680 6.720 20.160
8 504 3.024 15.120 60.480
9 720 5.040 30.240 151.200
10 990 7.920 55.400 332.640 6.652.800
11 1.320 11.880 95.040 665.280 3.991.680 19.958.400
12 1.716 17.160 154.440 1.235.520 8.648.640 51.891.840
13 2.184 24.024 240.240 2.162.160 17.297.280 121.080.960
References
[9]V.Faber and J.W.Moore, High-degree low-diameter interconnection networks with vertex symmetry:the directed case. Technical Report LA-UR-88-1051, Los Alamos National Laboratory, Los Alamos, New Mexico, 1988.
[14]M.Jiang and F.Ruskey, On the hamiltonicity of Faber-Moore graphs. Technical Report, University of Victoria, Victoria, B.C., Canada, 1992.
F. Comellas and M.A. Fiol, Vertex symmetric digraphs with small diameter., Discrete Applied Mathematics, vol. 58 (1995), pp. 1-12.

DIGRAPH COMPOSITION TECHNIQUE

Most of the graphs in the table with diameter 7, 9 and 11 have been found by applying this technique wich is based in the next theorem
Theorem If there is a vertex symmetric delta-regular k-reachable digraph with N vertices then, for all positive integers n and m a multiple of n, there exists a vertex symmetric (delta)-regular digraph with mN^n vertices and diameter at most kn+m-1.

Proof:We give here just the construction of the digraph. If G=(V,A) is a digraph satisfying the hypotheses of the theorem the new digraph G'=(V', A') is constructed as follows. The vertex set V' has elements (alfa | p_0p_1...p_(n-1) ) with alfa is in Z/mZ and p_i's are in V. The adjacencies of G' are: A vertex (alfa | p_0p_1...p_(alfa')...p_(n-1) ) is adjacent to the vertex (alfa+1 | p_0p_1...q_(alfa')...p_(n-1) ) where alfa'=alfa mod n and q_(alfa') is adjacent from p_(alfa') in G.
The family of cycle prefix digraphs Gamma_Gamma(D) are vertex-symmetric Gamma-regular digraphs whith diameter D and order (Gamma+1)!/ (Gamma+1-D)!
They also are D-reachable as we show in the next theorem

TheoremThe digraphs Gamma_Gamma(D) are D-reachables for D>=3.

Proof: Since they are vertex symmetric it suffices to prove that the distance from any vertex to the vertex labeled 123...D is exactly D. Let us start from vertex x_1x_2...x_D. We consider two cases according x_D is 1 or not.
Note:
A more detailed analysis about this technique and the complete proofs can be found in Vertex symmetric digraphs with small diameter., Discrete Applied Mathematics, vol. 58 (1995), pp. 1-12 , by F. Comellas and M.A. Fiol.

Now, we show the application of the above results.
In particular, if we take Gamma_Gamma(3) which is a vertex symmetric, Gamma-regular and 3-reachable digraph with N= (Gamma+1)!/ (Gamma+1-3)! vertices and we apply digraph composition with m=2 and n=2, we obtain a new vertex symmetric Gamma-regular digraph with order 2*N^2 and diameter 7=3*2+2-1 as shown in the next table:

Delta D Order
2|Gamma_3(3)|^2 3 7 1.152 2*24^2
2|Gamma_4(3)|^2 4 7 7.200 2*60^2
2|Gamma_5(3)|^2 5 7 28.800 2*120^2
2|Gamma_6(3)|^2 6 7 88.200 2*210^2
2|Gamma_7(3)|^2 7 7 225.792 2*336^2
2|Gamma_8(3)|^2 8 7 508.032 2*504^2
2|Gamma_9(3)|^2 9 7 1.036.800 2*720^2
2|Gamma_10(3)|^2 10 7 1.960.200 2*990^2


Also, if we take Gamma_Gamma(4) which is a vertex symmetric, Gamma-regular and 4-reachable digraph with N= (Gamma+1)!/ (Gamma+1-4)! vertices and we apply digraph composition with m=2 and n=2, we obtain a new vertex symmetric Gamma-regular digraph with order 2*N^2 and diameter 9=4*2+2-1 as shown in the next table:

Delta D Order
2|Gamma_5(4)|^2 5 9 259.200 =2*360^2
2|Gamma_6(4)|^2 6 9 1.411.200 =2*840^2
2|Gamma_7(4)|^2 7 9 5.644.800 =2*1680^2
2|Gamma_8(4)|^2 8 9 18.289.152 =2*3024^2
2|Gamma_9(4)|^2 9 9 50.803.200 =2*5040^2
2|Gamma_10(4)|^2 10 9 125.452.800 =2*7920^2
2|Gamma_11(4)|^2 11 9 282.268.800 =2*11880^2
2|Gamma_12(4)|^2 12 9 588.931.200 =2*17160^2
2|Gamma_13(4)|^2 13 9 1.154.305.152 =2*24024^2

Finally, if we take Gamma_Gamma(3) which is a vertex symmetric, Gamma-regular and 3-reachable digraph with N= (Gamma+1)!/ (Gamma+1-3)! vertices and we apply digraph composition with m=3 and n=3, we obtain a new vertex symmetric Gamma-regular digraph with order 3*N^3 and diameter 11=3*3+3-1 .
Another way to obtain diameter 11 is by Gamma_Gamma(5) applying digraph composition with m=2 and n=2, as shown in the next table:

Delta D Order
3|Gamma_3(3)|^3 3 11 41.472 =3*24^3
3|Gamma_4(3)|^3 4 11 648.000 =3*60^3
3|Gamma_5(3)|^3 5 11 5.184.000 =3*120^3
3|Gamma_6(3)|^3 6 11 27.783.000 =3*210^3
3|Gamma_7(3)|^3 7 11 113.799.168 =3*336^3
2|Gamma_8(5)|^2 8 11 457.228.800 =2*15120^2
2|Gamma_9(5)|^2 9 11 1.828.915.200 =2*30240^2
2|Gamma_10(5)|^2 10 11 6.138.320.000 =2*55400^2
2|Gamma_11(5)|^2 11 11 18.065.203.200 =2*95040^2
2|Gamma_12(5)|^2 12 11 47.703.427.200 =2*154440^2
2|Gamma_13(5)|^2 13 11 115.430.515.200 =2*240240^2

GENERALIZED DIGRAPH COMPOSITION TECHNIQUE

Most of the graphs in the table with diameter 10 have been found by applying this technique wich is based in the next theorem:
Theorem If there is a vertex symmetric delta-regular k-reachable digraph with N vertices then, for all positive integers n, m a multiple of n and b there exists a vertex symmetric (delta+1)-regular digraph with mN^n vertices and diameter kn+d with d being the diameter of the fixed 2-step digraph Cay(Z/mZ, {1,b}).

Proof:We give here just the construction of the digraph. If G=(V,A) is a digraph according to the hypothesis of the theorem the new digraph G'=(V', A') is constructed as follows. The vertex set V' has elements (alfa | p_0p_1...p_(n-1) ) with alfa is in Z/mZ and p_i are in V. The arcs in A' are given by: A vertex (alfa | p_0p_1...p_(alfa')...p_(n-1) ) is adjacent to the vertex (alfa+1 | p_0p_1...q_(alfa')...p_(n-1) ) and (alfa+b | p_0p_1...p_(alfa')...p_(n-1) ) where alfa'=alfa (mod n) and q_(alfa') is adjacent from p_(alfa') in G. The step b is chosen in order to minimize d.
The family of cycle prefix digraphs Gamma_Gamma(D) are vertex-symmetric Gamma-regular digraphs whith diameter D and order (Gamma+1)!/ (Gamma+1-D)!
They also are D-reachable as we have prove

Note:
A more detailed analysis about this technique and the complete proofs can be found in Vertex symmetric digraphs with small diameter., Discrete Applied Mathematics, vol. 58 (1995), pp. 1-12 , by F. Comellas and M.A. Fiol.

Now, we show the application of the above results.
In particular, if we take Gamma_Gamma(3) which is a vertex symmetric, Gamma-regular and 3-reachable digraph with N= (Gamma+1)!/ (Gamma+1-3)! vertices and we apply the generalized digraph composition with m=3 and n=3, we obtain a new vertex symmetric (Gamma+1)-regular digraph with order 3*N^3 and diameter 10=3*2+1, being 1 the diameter of the fixed 2-step digraph Cay(Z/3Z, {1,2})
as shown in the next table:

Delta D Order
3|Gamma_5(3)|^3 C 6 10 5.184.000 =3*120^3
3|Gamma_6(3)|^3 C 7 10 27.783.000 =3*210^3
3|Gamma_7(3)|^3 C 8 10 113.799.168 =3*336^3
3|Gamma_8(3)|^3 C 9 10 384.072.192 =3*504^3
3|Gamma_9(3)|^3 C 10 10 1.119.744.000 =3*720^3
3|Gamma_10(3)|^3 C 11 10 2.910.897.000 =3*990^3
3|Gamma_11(3)|^3 C 12 10 6.899.904.000 =3*1320^3
3|Gamma_12(3)|^3 C 13 10 15.159.089.098 =3*1716^3

SEMIDIRECT PRODUCT OF CYCLIC GROUPS

Vertex-transitive digraphs can be obtained by constructing the Cayley digraph of a group G relative to a generating set X. The elements of the group G form the set of vertices of the Cayley digraph Cay(G,X) , there is an arc from g to h if h=gx for some x in X.
As shown in [1] semidirect products of cyclic groups can be used to construct large graphs, which in turn result to be vertex-transitive
The results presented have been produced by computer search. Once proposed the semidirect product group various sets of possible generators sets are tested to check if the group is a good candidate. If so, the set of generators is changed in order to improve.

(delta,D) Order Group Generators Order of Generators
(3,5) 165 5*(4)33 [4,17], [4,4], [2,21] 15, 15, 5
(3,8) 1.860 12*(88)155 [8,108], [1,93], [11,68] 15, 12, 12
(3,9) 4.446 18*(4)247 [12,50], [7,125], [10,231] 39, 18, 9
(3,10) 10.849 19*(407)571 [2,19], [7,480], [15,502] 19, 19, 19
(4,4) 168 6*(3)28 [4,3], [0,12], [1,22], [1,3] 12, 7, 6, 6
(4,5) 444 12*(8)37 [5,33], [11,25], [10,17], [3,18] 12, 12, 6, 4
(4,6) 1.260 12*(2)105 [9,87], [4,89], [7,8], [10,45] 28, 15, 12, 6
(4,8) 12.090 30*(4)403 [5,165], [12,285], [1,92], [22,39] 186, 65, 30, 15
(4,9) 38.134 46*(180)829 [15,507], [18,276], [6,637], [22,542] 46, 23, 23, 23
(4,10) 132.012 36*(1593)3667 [23,1710], [26,3100], [14,707], [15,2346] 36, 18, 18, 12
(5,6) 3.582 18*(37)199 [5,13], [16,53], [8,123], [14,34], [15,110] 18, 9, 9, 9, 6
(5,8) 54.505 55*(512)991 [17,201], [43,230], [49,898], [27,951], [9,528] 55, 55, 55, 55, 55
(5,10) 752.914 194*(2069)3881 [183,1044], [30,1822], [184,1253], [188,1265], [160,2480] 194, 97, 97, 97, 97
(6,8) 170.898 78*(1236)2191 [48,79], [66,76], [17,998], [7,872], [40,1389], [34,1491] 91, 91, 78, 78, 39, 39
(7,8) 521.906 154*(700)3389 [139,798], [71,2968], [50,3016], [48,1301], [33,2433], [70,2042], [56,1956] 154, 154, 77, 77, 14, 11, 11
(8,8) 1.371.582 414*(408)3313 [305,241], [95,1838], [193,353], [287,650], [224,138], [102,3186], [330,2254], [153,1940] 414, 414, 414, 414, 207, 69, 69, 46
(9,8) 2.965.270 770*(32)3851 [419,1605], [431,3461], [194,3715], [514,1381], [334,943], [296,304], [755,2906], [623,3338], [60,733] 770, 770, 385, 385, 385, 385, 154, 110, 77
[1] Dinneen,M.J. & Hafner,P.; New results for the degree/diameter problem. Networks, 24 (1994) 359-367.

Hafner,P.R. Large Cayley graphs and digraphs with small degree and diameter. CDMTCS-005 Research Report Series (June 1994)

Substitution technique

The graphs in the table with diameter 8 and degres 4 to 12 have been found by José Gómez by a substitution technique

Personal Communication. Publication submitted 2004.