Vertex Symmetric Digraphs with Small Diameter ^{∗}

F. Comellas and M. A. Fiol Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya ETSE Telecomunicació, Girona Salgado s/n 08034 Barcelona, Catalonia, Spain

Received 18 August 1990; revised 5 March 1992

\begin{matrix}c \\ ◯ \end{matrix}1995 by Elsevier Science B.V. Discrete Applied Mathematics, 58, pp. 1–11 (1995).

Abstract

There is increasing interest in the design of dense vertex symmetric graphs and digraphs as models of interconnection networks for implementing parallelism. In these systems many nodes are connected with relatively few links and short paths between them and each node may execute, without modifications, the same communication software. In this paper we give new families of dense vertex symmetric (Δ, D) digraphs, that is large digraphs with a given maximum out-degree Δ and diameter at most D. The digraphs are derived from a certain family of digraphs on alphabets, proposed by Faber and Moore [8], with new construction techniques that generalize previous results from Conway and Guy [5]. With these families we have made important updates in the table of largest known vertex symmetric (Δ, D) digraphs.

1 Introduction

The construction of large graphs and digraphs of a given maximum degree and diameter is an area of considerable interest for its applications to the design of large interconnection networks, particularly for the construction of massive parallel computers. Other applications include the design of local area networks, the problem of data alignment and the description of some cryptographic protocols. Since 1964, when Elpas [7] studied the topological aspects of the construction of optimal large interconnection networks from a graph-theoretical point of view, this problem has attracted considerable attention. In this context it is known as the (Δ, D)-problem. Much work has been done for the undirected case, see [1] for a survey. Some interesting results correspond to Cayley graphs which, as it is known, are vertex symmetric [4, 6]. Actually, most networks related to parallel systems (hypercubes, grids, butterfly networks, ...) may be modelled by Cayley graphs. For directed graphs there are well known results concerning bounds [18, 2] and infinite families [3, 15, 16, 10] but the digraphs are vertex symmetric only in some special cases.

∗Research supported by the Comisión Interministerial de Ciencia y Tecnología under Project TIC90-0712.

The search for large digraphs which have the additional property of being vertex symmetric has been considered more recently. Faber and Moore in [8], for example, study families of digraphs on permutations and give a table of the largest known vertex symmetric (Δ, D) digraphs. More recently Dinneen [6] updated the table with constructions based on Cayley graphs from linear groups and semi-direct products of cyclic groups. The interest in vertex symmetric digraphs comes from the fact that in the associated network each node is able to execute the same communication software without modifications. In this way these digraphs may be considered in order to obtain an easy implementation of parallelism.

In this paper we give new families of large vertex symmetric (Δ, D) digraphs improving considerably the known results. Section 2 is devoted to notation and some previous results concerning digraphs on permutations. In Section 3 we describe some generalizations of a result from Conway and Guy [5] that are used in Section 4 for the construction of large vertex symmetric digraphs from certain smaller digraphs. In that section we also study some properties of the Faber and Moore digraphs and prove a conjecture proposed by them. Finally, we give an updated table of the largest known vertex symmetric (Δ, D) digraphs.

2 Notation and previous results

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 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 δ^{+}(x) is the number of vertices adjacent from x, the in-degree of a vertex δ^{−}(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∈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

1 + Δ + Δ^{2} + ⋯ + Δ^{D} = \frac{Δ^{D+1} − 1}{Δ − 1} = N(Δ, D)

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(Δ, D) vertices and diameter D [18, 2].

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 in this article 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 [15, 16]. The Kautz digraph K(Δ, D), Δ ≥ 2, has vertices labeled with words x_{1}x_{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_{1}x_{2} ⋯ x_{D} is adjacent to the Δ vertices x_{2} ⋯ x_{D}x_{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 [6] 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 [8] give a family of large vertex symmetric digraphs which they call Γ_{Δ}(D). These digraphs may be defined as digraphs on alphabets in the following way: The vertices are labeled with different words of length D, x_{1}x_{2} ⋯ x_{D}, such that they form a D-permutation of an alphabet of Δ + 1 letters. The adjacencies are given by

x_{1}x_{2} ⋯ x_{D} → \{ \begin{matrix}x_{2}x_{3}x_{4} ⋯ x_{D}x_{D+1}, & x_{D+1} ≠ x_{1}, x_{2}, …, x_{D} \\ x_{2}x_{3}x_{4} ⋯ x_{D}x_{1} \\ x_{1}x_{3}x_{4} ⋯ x_{D}x_{2} \\ x_{1}x_{2}x_{4} ⋯ x_{D}x_{3} \\ … \\ x_{1}x_{2}x_{3} ⋯ x_{D}x_{D−1} \end{matrix}

These digraphs have order (Δ + 1)_{D} = \frac{(Δ+1)!}{(Δ−D+1)!}, diameter D and are Δ-regular (Δ ≥ D). These digraphs are also Hamiltonian [14]. Note that the digraphs Γ_{Δ}(2) are in fact the Kautz digraphs K(Δ, 2). In the table of large vertex symmetric (Δ, D) digraphs, the digraphs Γ_{Δ} constitute most of the entries of its lower triangular part, that is digraphs with Δ > D, (D < 7).

A digraph is k-reachable if for every pair of vertices x, y ∈ V there exists a path of exactly k arcs from x to y. See [9, 17] for more details about k-reachable digraphs. As an example, the Kautz digraphs of diameter D are (D + 1)-reachable. Figure 1 shows K(2, 2). In this figure a line represents two opposite arcs.

[figure]

Figure 1: K(2, 2), a 3-reachable 2-regular vertex symmetric digraph with diameter 2.

The maximum order of a k-reachable Δ−regular digraphs is Δ^{k}. It is easy to prove that this bound is not attained for vertex symmetric digraphs when k > 1 and Δ > 1. Indeed, in order to attain it we should have A^{k} = J, where A is the adjacency matrix of the digraph and J is the matrix with all entries equal to 1. Besides, as the digraph is Δ−regular the eigenvalues of A are 0 and Δ (Δ with multiplicity one). Thus the trace of A is Δ and the digraph has exactly Δ loops, which is incompatible with symmetry.

The following section presents a digraph composition technique which uses kreachable digraphs to construct large vertex symmetric digraphs.

3 Digraph composition

In this section we give a generalization of a theorem from Conway and Guy [5] which is used in Section 4 for constructing families of large vertex symmetric digraphs from the digraphs Γ_{Δ}(D).

Theorem 1. If there is a vertex symmetric Δ−regular k-reachable digraph with N vertices then, for all n and m a multiple of n, there exists a vertex symmetric Δ-regular digraph with mN^{n} vertices and diameter at most kn + m − 1^{1}.

Proof: Let G = (V, A) be a digraph satisfying the hypotheses of the theorem. A new digraph G′ = (V′, A′) may be constructed as follows: The vertex set V′ has elements (α | p_{0}p_{1} ⋯ p_{n−1}) with α ∈ Z/mZ and p_{i} ∈ V. The adjacencies of G′ are:

(α | p_{0}p_{1} ⋯ p_{α} ⋯ p_{n−1}) → (α + 1 | p_{0}p_{1} ⋯ q_{α} ⋯ p_{n−1})

where all the indices of the vertices of G are taken modulo n and q_{α} is adjacent from p_{α} in G. We shall prove that G′ is vertex symmetric and has diameter at most kn + m − 1.

• G′ is vertex symmetric: Let ϕ_{0}, ϕ_{1}, …, ϕ_{n−1} be automorphisms of G = (V, A) and let t be any element of Z/mZ. The graph G′ is vertex symmetric since the map ψ

(α | p_{0}p_{1} ⋯ p_{n−1}) ↦^{ψ} (α − t | ϕ_{0}(p_{t})ϕ_{1}(p_{t+1}) ⋯ ϕ_{n−1}(p_{t+n−1}))

1Conway and Guy proved the case m = n.

is an automorphism of G′. Indeed,

ψ(α | p_{0}p_{1} ⋯ p_{α} ⋯ p_{n−1}) =
(α − t | ϕ_{0}(p_{t})ϕ_{1}(p_{t+1}) ⋯ ϕ_{α−t}(p_{α}) ⋯ ϕ_{n−1}(p_{t+n−1})) →
(α − t + 1 | ϕ_{0}(p_{t})ϕ_{1}(p_{t+1}) ⋯ ϕ_{α−t}(q_{α}) ⋯ ϕ_{n−1}(p_{t+n−1})) =
ψ(α + 1 | p_{0}p_{1} ⋯ q_{α} ⋯ p_{n−1})

where we have used that, in G, p_{α} → q_{α} ⇔ ϕ_{α−t}(p_{α}) → ϕ_{α−t}(q_{α}).

• G′ has diameter at most kn + m − 1: If we wish to find a path from (α | p_{0}p_{1} ⋯ p_{n−1}) to (β | q_{0}q_{1} ⋯ q_{n−1}) let us consider ξ = β − α − kn (mod m). After ξ steps the vertex attained is (α + ξ | r_{0}r_{1} ⋯ r_{n−1}). As, in G, from each r_{i} we may reach q_{i} with exactly k steps, by performing kn steps we reach (α + ξ + kn | q_{0}q_{1} ⋯ q_{n−1}), but α + ξ + kn = β (mod m). So, the total number of steps is not greater than kn + m − 1. □

If we replace each vertex of the Kautz digraph K(Δ, 2) by two copies of K_{2}^{∗} (the complete symmetric digraph on 2 vertices), and each arc (x, y) by the structure of Figure 2, we obtain a vertex symmetric 2-reachable (2Δ + 1)-regular digraph with the maximum possible order (2Δ + 1)^{2} − 1, [12]. Figure 3 shows the eight vertex digraph obtained when Δ = 1 (in this case K(1, 2) = K_{2}^{∗}). For Δ = 3 the resulting digraph is 5-regular and has 24 vertices, then, by Theorem 1 with m = n = 2, we obtain a new large vertex symmetric (5, 5) digraph of order 1152.

[figure: y; x]

Figure 2: Arc replacement for K(Δ, 2).

[figure]

Figure 3: A 2-reachable vertex symmetric digraph with 8 vertices.

A modification of the above construction, that increases the degree, is also useful for improving some values of the table. This modification is based on fixed 2-step digraphs, that is the Cayley digraphs Cay(Z/mZ, {1, b}), see [11].

Theorem 2. If there is a vertex symmetric Δ-regular k-reachable digraph with N vertices then, for all positive integers b, n and m a multiple of n, there exists a vertex symmetric (Δ+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: The proof follows similar steps to those in Theorem 1. 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 (α | p_{0}p_{1} ⋯ p_{n−1}) with α ∈ Z/mZ and p_{i} ∈ V. The arcs of A′ are given by

(α | p_{0}p_{1} ⋯ p_{α} ⋯ p_{n−1}) → \{ \begin{matrix}(α + 1 | p_{0}p_{1} ⋯ q_{α} ⋯ p_{n−1}) \\ (α + b | p_{0}p_{1} ⋯ p_{α} ⋯ p_{n−1}) \end{matrix}

where q_{α} is adjacent from p_{α} in G. The step b is chosen in order to minimize d. A list of convenient values of b for each m may be found in [11]. □

Further generalizations would be possible by using an s-step digraph, s ≥ 3, to describe the possible changes of α.

Another interesting generalization of the previous results is the following:

Theorem 3. Let G = (V, A) be a vertex symmetric Δ-regular k-reachable digraph with N vertices. Let Cay(H, S) be a Cayley digraph with diameter d. If for some subgroup K of H there exists an element s ∈ S such that H = K∪sK∪s^{2}K∪⋯∪s^{n−1}K, n = |H : K|, then there exists a vertex symmetric digraph with degree Δ + |S| − 1, order |H|N^{n}, and diameter kn + d.

Proof: The new digraph, G′ = (V′, A′) is constructed as follows: The vertex set V′ has elements (α | p_{0}p_{1} ⋯ p_{n−1}) with α ∈ H and p_{i} ∈ V. The adjacencies are

(α | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1}) → \{ \begin{matrix}(αs | p_{0}p_{1} ⋯ q_{σ(αK)} ⋯ p_{n−1}) \\ (αt | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1}) & ∀t ∈ S \ s \end{matrix}

where q_{σ(αK)} is adjacent from p_{σ(αK)} in G and the map σ : {K, sK, s^{2}K, …, s^{n−1}K} → Z/nZ is defined as σ(s^{i}K) = i. Clearly, the order of this graph is |V′| = |H|N^{n} and the digraph is regular with degree Δ + |S| − 1. We shall prove that G′ is vertex symmetric and has diameter kn + d.

• G′ is vertex symmetric: Let ϕ_{0}, ϕ_{1}, …, ϕ_{n−1} be automorphisms of G = (V, A) and let u be any element of H. The graph G′ is vertex symmetric since the map ψ,

(α | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1}) ↦^{ψ}

(u^{−1}α | ϕ_{0}(p_{σ(uK)})ϕ_{1}(p_{σ(usK)}) ⋯ ϕ_{l}(p_{σ(αK)}) ⋯ ϕ_{n−1}(p_{σ(us^{n−1}K)})) where l = σ(u^{−1}αK) because of αK = us^{l}K, is an automorphism of G′. Indeed,

ψ((α | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1})) =

(u^{−1}α | ϕ_{0}(p_{σ(uK)})ϕ_{1}(p_{σ(usK)}) ⋯ ϕ_{σ(u^{−1}αK)}(p_{σ(us^{σ(u^{−1}αK)}K)}) ⋯ ϕ_{n−1}(p_{σ(us^{n−1}K)})) →

(u^{−1}αs | ϕ_{0}(p_{σ(uK)})ϕ_{1}(p_{σ(usK)}) ⋯ ϕ_{σ(u^{−1}αK)}(q_{σ(us^{σ(u^{−1}αK)}K)} ⋯ ϕ_{n−1}(p_{σ(us^{n−1}K)})) =

ψ((αs | p_{0}p_{1} ⋯ q_{σ(αK)} ⋯ p_{n−1}))

where we have used that, in G, p_{i} → q_{i} ⇔ ϕ_{j}(p_{i}) → ϕ_{j}(q_{i}); and ψ((α | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1})) = ψ((αt | p_{0}p_{1} ⋯ p_{σ(αK)} ⋯ p_{n−1})) ∀t ∈ S \ s.

• G′ has diameter at most kn + d: To find a path from (α | p_{0}p_{1} ⋯ p_{n−1}) to (β | q_{0}q_{1} ⋯ q_{n−1}) let us consider ξ = α^{−1}βs^{−kn}. After at most d steps we attain (αξ | r_{0}r_{1} ⋯ r_{n−1}). As, in G, from each r_{i} we may attain q_{i} with exactly k steps, by performing kn steps we reach (αξs^{kn} | q_{0}q_{1} ⋯ q_{n−1}), but αξs^{kn} = β. So, the total number of steps is not greater than kn + d. Moreover, if the Cayley digraph is m-reachable the new digraph is (kn + m)- reachable.□

4 New families of large vertex symmetric digraphs

In this section we first show that the vertex symmetric digraphs Γ_{Δ}(D) [8] are Dreachable. We then apply the main result of Section 3 and construct new large families of vertex symmetric digraphs. We also prove a conjecture of Faber and Moore [8] concerning the construction of new large families of vertex symmetric digraphs from the digraphs Γ_{Δ}(D) by removing some adjacencies. Finally, an updated version of the table of largest known vertex symmetric (Δ, D) digraphs is given.

Theorem 4. The digraphs Γ_{Δ}(D) are D-reachable for D ≥ 3.

Proof: As the digraphs 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_{1}x_{2} ⋯ x_{D}. We consider two cases according to the fact that x_{D} is different or not from 1.

(a) x_{D} ≠ 1. At the first step we clearly may reach the vertex x_{2}x_{3} ⋯ x_{D}1 and from it we successively reach vertices ending in 12, 123, …, 123 ⋯ D. After exactly D steps we reach the desired vertex.

(b) x_{D} = 1. In this case, at the first step we go to a vertex that ends with symbol y = x_{D+1} ≥ 3, y ≤ D. This is always possible because Δ ≥ D ≥ 3. Next adjacencies lead to vertices which successively end in 1y2, 1y23, …, 1y23 ⋯ (y−1), 123 ⋯ (y−1)y, …, 123 ⋯ D. Therefore precisely D steps are used to reach 123 ⋯ D. □

It is now possible to apply the results of Section 2 to these digraphs. The most interesting values correspond to use the 3-reachable digraphs Γ_{Δ}(3), Δ ≥ 3. From them, and applying Theorem 1, it is possible to construct large vertex symmetric digraphs with diameters 7 (order 2|Γ_{Δ}(3)|^{2}) and 11 (order 3|Γ_{Δ}(3)|^{3}). Considering Γ_{Δ}(4) with Δ ≥ 4 we obtain digraphs with diameter 9 and order 2|Γ_{Δ}(4)|^{2}. Theorem 2 with m = n = 3 and b = 2 (d = 1), may be applied to Γ_{Δ}(3) to obtain digraphs with diameter 10 and order 3|Γ_{Δ}(3)|^{3} .

Another way of constructing new families of large vertex symmetric (Δ, D) digraphs from the digraphs Γ_{Δ}(D) consists of removing one of their adjacencies. In [8], Faber and Moore proved that, in this case, the diameter increases just by one. They conjectured that the removal of more adjacencies also leads to a moderate increment of the diameter. The following result proves this conjecture.

Let Γ_{Δ}(D, −(r − 1)), Δ ≥ D ≥ 2r ≥ 4, be the digraph Γ_{Δ}(D) with the last r − 1 adjacencies removed. That is,

x_{1}x_{2} ⋯ x_{D−r}x_{D−r+1} ⋯ x_{D−1}x_{D} → \{ \begin{matrix}x_{2}x_{3}x_{4} ⋯ x_{D}x_{D+1}, & x_{D+1} ≠ x_{1}, x_{2}, …, x_{D} \\ x_{2}x_{3}x_{4} ⋯ x_{D}x_{1} \\ x_{1}x_{3}x_{4} ⋯ x_{D}x_{2} \\ x_{1}x_{2}x_{4} ⋯ x_{D}x_{3} \\ … \\ x_{1}x_{2}x_{3} ⋯ x_{D}x_{D−r} \end{matrix}

This digraph has degree Δ − r + 1.

Theorem 5. The digraph Γ_{Δ}(D, −(r − 1)), Δ ≥ D ≥ 2r ≥ 4, has diameter D + r − 1.

Proof: The digraph is vertex transitive, so it suffices to prove that from any vertex, x_{1}x_{2} ⋯ x_{D}, we may reach the vertex labeled with 123 ⋯ D with at most D + r − 1 steps. We divide the problem in two different cases according to the value of the last symbol x_{D}.

(a) x_{D} ≠ 1. In the first r − 1 steps we reach vertices ending successively in y_{1}, y_{1}y_{2}, …, y_{1}y_{2} ⋯ y_{r−1}. At this point we can reach vertices ending in the r digits y_{2} ⋯ y_{r−1}1, y_{3} ⋯ y_{r−1}12, …, y_{r−1}123 ⋯ (r − 1), 123 ⋯ r if y_{i} ≥ r + 1 for any i, 1 ≤ i ≤ r − 1. At each step the existence of such a y_{i} is assured if Δ + 1 − r ≥ r + 1, that is Δ ≥ 2r. Next adjacencies lead to vertices ending in 123 ⋯ (r + 1), …, 123 ⋯ D. The total number of steps performed is exactly D + r − 1.

(b) x_{D} = 1. As in case (a), and after r − 1 steps, we reach a vertex that ends in 1y_{1}y_{2} ⋯ y_{r−1}. From this vertex we can reach vertices ending in 1y_{1}y_{2} ⋯ y_{r−1}2, 1y_{1}y_{2}y_{3} ⋯ y_{r−1}23, …, 1y_{1}y_{2} ⋯ y_{r−1}23 ⋯ (r + 1) if y_{i} ≥ r + 2 for any i, 1 ≤ i ≤ r − 1. At each step the existence of such a y_{i} is assured if Δ + 1 − (r − 1) ≥ r + 2, that is Δ ≥ 2r. From vertex 1y_{1}y_{2} ⋯ y_{r−1}23 ⋯ (r + 1) it is possible to reach vertex 123 ⋯ D in D − (r + 1) more steps provided that the condition y_{i} ≤ D for any i, 1 ≤ i ≤ r − 1, is also satisfied. Hence another condition is D ≥ 2r. Vertex 123 ⋯ D will be reached in D + r − 2 steps. If, as in case (a), we want a path of lenght D + r − 1 we first go to a vertex ending in 1y_{1}y_{2} ⋯ y_{r} such that, as before D ≥ y_{i} ≥ r + 2, 1 ≤ i ≤ r, that is, D ≥ 2r + 1. So if this condition holds the digraph is also (D + r − 1)-reachable, Theorem 4 being the particular case r = 1.

Finally to show that the diameter is not less than D + r − 1, note that if the initial vertex ends in 1(Δ + 1), in some step digit 1 has to be placed at the rightmost position. But, for this purpose, at least r − 1 steps are necessary. Hence the distance from vertex x_{1}x_{2} ⋯ 1(Δ + 1) to vertex 123 ⋯ D is exactly D + r − 1.□

Table 1 is the updated table with all the new values added. The improvements that are a consequence of this paper are shown in boldface. One entry, N(2, 7) = 120, was found by different means. Simulated annealing on permutation digraphs, see [?], produced an arcsymmetric digraph (its automorphism group acts transitively on its set of arcs) with order 6 and diameter 2. The final vertex symmetric digraph was obtained by the line digraph technique, see [10].

Acknowledgement

The authors thank Charles Delorme for suggesting the generalization included as Theorem 3.

TABLE 1. LARGEST KNOWN VERTEX SYMMETRIC (Δ, D) DIGRAPHS

D 2  3  4  5  6  7  8  9  10  11

Δ

2  {K \atop 6}  {FM \atop 10}  {FM \atop 20} \begin{matrix}Z×_{σ}Z \\ 27 \end{matrix}  {H92 \atop 72}  {LD \atop 144}  {FM \atop 171}  {FM \atop 336}  {FM \atop 504}  {GL \atop 737}
3  {K \atop 12} \begin{matrix}Z×_{σ}Z \\ 27 \end{matrix}  {FM \atop 60} \begin{matrix}Z×_{σ}Z \\ 165 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 333 \end{matrix}  \begin{matrix}2G^{2} \\ 1 152 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 1 808 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 4 446 \end{matrix}  {GL \atop 8 736}  \begin{matrix}3G^{3} \\ 41 472 \end{matrix}
4  {K \atop 20}  {Γ \atop 60} \begin{matrix}Z×_{σ}Z \\ 168 \end{matrix} \begin{matrix}Z×_{σ}Z \\ 444 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 1 260 \end{matrix}  \begin{matrix}2G^{2} \\ 7 200 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 12 090 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 38 134 \end{matrix}  {GL \atop 105 456}  \begin{matrix}3G^{3} \\ 648 000 \end{matrix}
5  {K \atop 30}  {Γ \atop 120}  {Γ \atop 360} \begin{matrix}2G^{2} \\ 1 152 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 3 582 \end{matrix}  \begin{matrix}2G^{2} \\ 28 800 \end{matrix}  {GL \atop 50 616}  \begin{matrix}2G^{2} \\ 259 200 \end{matrix}  {GL \atop 688 800}  \begin{matrix}3G^{3} \\ 5 184 000 \end{matrix}
6  {K \atop 42}  {Γ \atop 210}  {Γ \atop 840}  {Γ \atop 2 520}  \begin{matrix}Z×_{σ}Z \\ 7 644 \end{matrix}  \begin{matrix}2G^{2} \\ 88 200 \end{matrix}  {GL \atop 151 848}  \begin{matrix}2G^{2} \\ 1 411 200 \end{matrix}  \begin{matrix}3G^{3}C \\ 5 184 000 \end{matrix}  \begin{matrix}3G^{3} \\ 27 783 000 \end{matrix}
7  {K \atop 56}  {Γ \atop 336} {Γ \atop 1680}  {Γ \atop 6 720}  {Γ \atop 20 160} \begin{matrix}2G^{2} \\ 225 792 \end{matrix}  {GL \atop 410 640}  \begin{matrix}2G^{2} \\ 5 644 800 \end{matrix}  \begin{matrix}3G^{3}C \\ 27 783 000 \end{matrix}  \begin{matrix}3G^{3} \\ 113 799 168 \end{matrix}
8  {K \atop 72}  {Γ \atop 504} {Γ \atop 3 024} {Γ \atop 15 120}  {Γ \atop 60 480} \begin{matrix}2G^{2} \\ 508 032 \end{matrix}  \begin{matrix}Z×_{σ}Z \\ 680 760 \end{matrix}  \begin{matrix}2G^{2} \\ 18 289 152 \end{matrix}  \begin{matrix}3G^{3}C \\ 113 799 168 \end{matrix}  \begin{matrix}2G^{2} \\ 457 228 800 \end{matrix}
9  {K \atop 90}  {Γ \atop 720} {Γ \atop 5 040} {Γ \atop 30 240} {Γ \atop 151 200} \begin{matrix}2G^{2} \\ 1 036 800 \end{matrix} \begin{matrix}Z×_{σ}Z \\ 1 822 176 \end{matrix}  \begin{matrix}2G^{2} \\ 50 803 200 \end{matrix}  \begin{matrix}3G^{3}C \\ 384 072 192 \end{matrix} \begin{matrix}2G^{2} \\ 1 828 915 200 \end{matrix}
10  {K \atop 110}  {Γ \atop 990} {Γ \atop 7920} {Γ \atop 55 400} {Γ \atop 332 640} \begin{matrix}2G^{2} \\ 1 960 220 \end{matrix} {Γ \atop 6 652 800} \begin{matrix}2G^{2} \\ 125 452 800 \end{matrix} \begin{matrix}3G^{3}C \\ 1 119 744 000 \end{matrix} \begin{matrix}2G^{2} \\ 6 138 320 000 \end{matrix}
11  {K \atop 132} {Γ \atop 1 320} {Γ \atop 11 800} {Γ \atop 95 040} {Γ \atop 665 280} {Γ \atop 3 991 680} {Γ \atop 19 958 400} \begin{matrix}2G^{2} \\ 282 268 800 \end{matrix} \begin{matrix}3G^{3}C \\ 2 910 897 000 \end{matrix} \begin{matrix}2G^{2} \\ 18 065 203 200 \end{matrix}
12  {K \atop 156} {Γ \atop 1 716} {Γ \atop 17 160} {Γ \atop 154 440} {Γ \atop 1 235 520} {Γ \atop 8 648 640} {Γ \atop 51 891 840} \begin{matrix}2G^{2} \\ 588 931 200 \end{matrix} \begin{matrix}3G^{3}C \\ 6 899 904 000 \end{matrix} \begin{matrix}2G^{2} \\ 47 703 427 200 \end{matrix}
13  {K \atop 182} {Γ \atop 2 184} {Γ \atop 24 024} {Γ \atop 240 240} {Γ \atop 2 162 160} {Γ \atop 17 297 280} {Γ \atop 121 080 960} \begin{matrix}2G^{2} \\ 1 154 305 152 \end{matrix} \begin{matrix}3G^{3}C \\ 15 159 089 098 \end{matrix} \begin{matrix}2G^{2} \\ 115 430 515 200 \end{matrix}

K  Kautz digraph [15, 16]
GL  Digraphs built from linear groups [6]
Z×_{σ}Z Digraphs built from semi-direct products of cyclic groups [6]
Γ  Digraph on permutations Γ_{Δ}(D) [8]
FM  Digraph found by computer search by Faber and Moore [8]
nG^{n}  Digraph composition (Theorem 1)
nG^{n}C Generalized digraph composition (Theorem 2)
LD  Line digraph of the arc symmetric digraph H92[13]

References

[1] J-C Bermond, C. Delorme and J.J. Quisquater, Strategies for interconnection networks: Some methods from Graph Theory. J. Parallel and Distrib. Comp. 3, pp. 433-449, 1986.

[2] W.G. Bridges and S. Toueg, On the impossibility of directed Moore graphs. J. Comb. Theory B. 29, pp. 339-341, 1980.

[3] N.G. de Bruijn, A combinatorial problem. Koninklijke Nederlandse Academie van Watenschappen Proc., A49, pp. 758-764, 1946.

[4] D.V. Chudnovsky, G.V. Chudnovsky and M.M. Denneau, Regular graphs with small diameter as models for interconnection networks. Proc. Third Int. Conf. on Supercomputing, ICS’88; Boston, May 16-20 1988, pp. 232-239.

[5] J.H. Conway and M.J.T. Guy, Message graphs. Ann. of Discrete Math., 13, pp. 61-64, 1982.

[6] M.J. Dinneen, Algebraic Methods for Efficient Network Constructions. Master Thesis, Department of Computer Science, University of Victoria, Victoria, B.C., Canada, 1991.

[7] B. Elpas, Topological constrains on interconnection limited logic. Proceedings 5th Symposium on Switching Circuit Theory and Logical Design, 5-164, pp. 133-197, IEEE, New York, 1964.

[8] 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.

[9] M.A. Fiol, I. Alegre, J. L. A. Yebra and J. Fàbrega, Digraphs with walks of equal length between vertices. Graph Theory with Applications to Algorithms and Computer Science, pp. 702-713, Edited by Y. Alavi et al. John Wiley & Sons, Inc. 1985.

[10] M.A. Fiol, J. L. A. Yebra and I. Alegre, Line digraph iterations and the (d, k) digraph problem. IEEE Trans. Comp. C-33, pp. 400-403, 1984.

[11] M.A. Fiol, J. L. A. Yebra, I. Alegre and M. Valero, A discrete optimization problem in local networks and data alignment. IEEE Trans. Comp. C-36, pp. 702-713, 1987.

[12] J. Gómez, Departament de Matemàtica Aplicada i Telemàtica, Universitat Politècnica de Catalunya. Personal communication (1992).

[13] P.R. Hafner, Department of Mathematics and Statistics, University of Auckland. Personal communication (1992).

[14] M. Jiang and F. Ruskey, Determining the Hamilton-connectedness of certain vertextransitive graphs. Discrete Math., to appear.

[15] W.H. Kautz, Bounds on directed (d, k) graphs. Theory of cellular logic 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 249-272, 1969.

[17] N.S. Mendelsohn, Directed graphs with the unique path property. Combinatorial Theory and its Applications II, Proc. Colloq. Balatonfürer, 1969, North Holland, 783-799, 1970.

[18] J. Plesník and S̆. Znám, Strongly geodetic directed graphs. Acta Fac. Rerum Natur. Univ. Comenian., Math. Publ. 29, pp. 29-34, 1974.