Broadcasting in Cycle Prefix Digraphs ⋆

F. Comellas^{a}, M. Mitjana^{b}

a Departament de Matemàtica Aplicada i Telemàtica, Universitat Politècnica de Catalunya, Campus Nord, C3, E-08034 Barcelona, Catalonia, Spain.

b Departament de Matemàtica Aplicada I, Universitat Politècnica de Catalunya, Gregorio Marañon 44, E-08028 Barcelona, Catalonia, Spain

Cycle prefix digraphs are directed Cayley coset graphs that have been proposed as a model of interconnection networks for parallel architectures. In this paper we present new details concerning their structure that are used to design a communication scheme leading to upper bounds on their broadcast time. When the diameter is two, the digraphs are Kautz digraphs and in this case our algorithm improves the known upper bounds for their broadcast time and is indeed optimal for small values of the degree.

Discrete Appl. Math., 82 (1–3), pp. 29–37, (1998).

Copyright (c) 1998 Elsevier Science B.V. All rights reserved.

1 Introduction.

A wide variety of new models for parallel architectures and distributed computing have been introduced in recent years. One important issue in their design and possible implementation is the topology of the associated network. The consideration of highly symmetric and dense interconnection networks, particularly for massively parallel computers, leads to a question of special interest in graph theory: the construction of vertex symmetric digraphs with order as large as possible for a given maximum degree and diameter. One important reason to consider vertex symmetric digraphs is that in the associated network each node is able to execute the same communication software. Other aspects of interest are their modularity and simple definition.

Most large vertex symmetric digraphs correspond to Cayley (coset) digraphs and have been found either by random computer search, special graph prod-

⋆ Research supported by the CICYT, Spain, under Project TIC94-0592 and the European Union HCM Program ERBCHRX-CT920049. F.C. acknowledges a grant (ref. PR95-179) from the Dirección General de Investigación Científica y Técnica, Ministerio de Educación y Ciencia, Spain.

Preprint submitted to Elsevier Preprint 2 March 1998

ucts, or direct constructions. Very often, vertex symmetric digraphs may be described as digraphs on alphabets. A digraph on an alphabet is constructed as follows: the vertices are labeled with words on the given alphabet and the arcs are defined according to a rule that relates two different words. This representation of the digraph facilitates the direct calculation of the diameter and other distance-related parameters. An interesting family of vertex symmetric digraphs was defined by Faber and Moore as Cayley coset digraphs [5] and may be viewed as well as a family of digraphs on alphabets [4,6]. This latter representation gives them the name that we will use through this paper: cycle prefix digraphs.

On the other hand, much work has been done related to the dissemination of information in interconnection networks. The importance of this research area lies in the fact that the ability of a network to effectively disseminate information is an important measure of the suitability of the network for parallel computing. Broadcasting is one of the most studied problems in communication networks and refers to the sending of a message from one node of the network to all the other nodes as quickly as possible, subject to the constraints that each call involves only two nodes, a node which already knows the message can only inform one of the nodes to which it is connected, and each call requires one unit of time.

In this paper we are interested in the study of communication schemes for cycle prefix digraphs. We present an efficient broadcasting scheme based on the recursive structure that we describe below.

The paper is organized as follows. The next section will introduce the notation and give some general definitions. Section 3 presents the cycle prefix digraphs and some of their properties. Then we focus on the recursive structure of the digraphs which will suggest the broadcast strategy presented in Section 4 together with the upper bounds on the broadcast time. Finally, in Section 5, we compare the broadcast time obtained with the known upper bounds for de Bruijn digraphs of similar order for the same diameter and degree. When the diameter is two, we also make a comparison with the upper bounds known for the corresponding Kautz family. We see that our scheme improves considerably the bounds given by Bermond and Peyrat [1] and by Heydemann, Opatrny and Sotteau [9], and is indeed optimal for small values of the degree.

2 Notation

Let Γ = (V, A) be a digraph with vertex set V and arc set A. The out-degree of a vertex u, δ^{+}(u), is the number of vertices adjacent from u and its indegree δ^{−}(u), is the number of vertices adjacent to u. A digraph is regular of degree Δ or Δ-regular if the in-degrees and out-degrees of all vertices equal Δ. We define a path in Γ from v_{0} ∈ V to v_{k} ∈ V as a sequence of abutting arcs (v_{0}, v_{1}), (v_{1}, v_{2}), ⋯, (v_{k−1}, v_{k}) such that for each i ∈ 0, 1, ⋯, k − 1, (v_{i}, v_{i+1}) ∈ E. A digraph is (strongly) connected if there is a path from every vertex to every other vertex.

A digraph is vertex symmetric if its automorphism group acts transitively on its set of vertices. A Cayley coset digraph, Cay(G, H, S), is a digraph defined by a finite group G, a subgroup H and a set of generators S ⊆ G \ H. The vertex set is given by the set of left cosets {gH|g ∈ G} and there is an arc (g_{1}H, g_{2}H) whenever g_{1}sH = g_{2}H for some s ∈ S. Cayley coset digraphs are |S|-regular, connected and vertex symmetric. Moreover, every vertex symmetric digraph is a Cayley coset digraph, as is shown in [13]. In particular, a Cayley coset digraph Γ is a Cayley digraph iff H = {e}, where e is the identity of G.

Γ = Cay(G, H, S) is a hierarchical or quasi-minimal Cayley coset digraph iff there is an ordering of the elements of S, say {s_{1}, s_{2}, ⋯, s_{k}} such that for every i = 1, 2, ⋯, k − 1, the group ⟨H, s_{1}, s_{2}, ⋯, s_{i}⟩ is a proper subgroup of ⟨H, s_{1}, s_{2}, ⋯, s_{i}, s_{i+1}⟩. Γ is minimal iff for no S′ ⊂ S, ⟨H, S′⟩ = G. A hierarchical Cayley (coset) digraph can be decomposed into a collection of isomorphic subdigraphs along with edges connecting them. Each subdigraph is a smaller Cayley (coset) digraph.

Broadcasting in a graph is the process of spreading a message known initially by one vertex, subject to the following rules. The transfer of the message from one vertex to another (termed a call) takes one unit of time. A vertex can only call an adjacent vertex. A vertex can participate in at most one call per unit of time. A broadcast scheme is a formal description of this process.

Given a connected digraph Γ and a vertex u, the broadcast time of u, denoted b(u), is the minimum number of time units required to broadcast a message originating at u. The broadcast time of the graph Γ is defined b(Γ) = max{b(u)|u ∈ Γ}. For any vertex u in a connected graph with |V | vertices, b(u) ≥ ⌈log_{2} |V |⌉, since during each time unit the number of vertices informed can at most double. For a vertex symmetric graph, the broadcast time is equal to the broadcast time of any of its vertices.

The de Bruijn digraph B(Δ, D), Δ ≥ 2, has vertices labeled with words x_{1}x_{2} ⋯ x_{D} where x_{i} belongs to an alphabet of size Δ. There is an arc from any vertex x_{1}x_{2} ⋯ x_{D} to the Δ vertices x_{2} ⋯ x_{D}x_{D+1}, where x_{D+1} is any letter of the alphabet. B(Δ, D) is Δ-regular, has Δ^{D} vertices and diameter D.

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. Figure 1 shows K(2, 2) (in the figures of this paper a line represents two opposite arcs).

[figure: 20; 02; 21; 10; 12; 01]

Fig. 1. K(2,2), a 2-regular vertex symmetric digraph with diameter 2.

3 Cycle prefix digraphs. Recursive structure.

The cycle prefix digraphs Γ_{Δ}(D), Δ ≥ D, were introduced as Cayley coset digraphs by Faber and Moore in 1988 [5]. These digraphs may also be defined on an alphabet of Δ + 1 symbols as follows [4,6]: Each vertex x_{1}x_{2} ⋯ x_{D} is a sequence of distinct symbols from the alphabet. 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_{1}x_{2} ⋯ x_{k−1}x_{k+1} ⋯ x_{D}x_{k}, & 1 ≤ k ≤ D − 1 \end{matrix}

The first kind of adjacency, that introduces a new symbol, will be called a shift. The other adjacencies will be called rotations. Γ_{Δ}(D) has order (Δ+1)_{D}, diameter D and is Δ-regular (Δ ≥ D).

Cycle prefix digraphs have several relevant properties which are of interest when modelling an interconnection network. The digraphs are Hamiltonian, as was proved by M. Jiang and F. Ruskey in [11]. In [4], Comellas and Fiol proved that, for D ≥ 3, the digraphs are D−reachable (every pair of vertices, not necessarily different, may be joined by a path of exactly D arcs). Together with new families constructed from them, cycle prefix digraphs have provided important improvements to the table of largest known vertex-symmetric (Δ, D) digraphs, see [4]. It has been shown by Chen, Faber and Knill [3] that the wide diameter of Γ_{Δ}(D) is D + 2 (the wide diameter of a graph is considered an important measure of communication efficiency and reliability, see [10]). By extending a former result for hierarchical Cayley graphs from Hamidoune, Lladó and Serra [8] to this particular family of Cayley coset digraphs, Knill, in [12], showed that the cycle prefix digraphs have optimal connectivity.

Some hierarchical Cayley graphs can be recursively decomposed. This is the case for the pancake and star graphs (see GowriSankaran [7] and Berthomé, Ferreira and Perennes [2]). By using the description as digraphs on an alphabet it is also possible to give a recursive decomposition for the cycle prefix digraphs. The following lemma summarizes this result.

Lemma 1 The cycle prefix digraph Γ_{Δ}(D) decomposes into \binom{Δ+1}{D} subdigraphs, each isomorphic to Γ_{D−1}(D − 1).

PROOF. Let us consider all vertices of Γ_{Δ}(D) which have the same set of symbols, together with their corresponding edges. Clearly, they form a subdigraph that is isomorphic to Γ_{D−1}(D − 1). Since there are \binom{Δ+1}{D} possible different ways of choosing this set of symbols from the given alphabet, we can express Γ_{Δ}(D) as a vertex disjoint union of \binom{Δ+1}{D} subdigraphs. □

Figure 2 shows one of the subdigraphs that can be obtained from Γ_{Δ}(4). Note that, for clarity, we have omitted some edges that join the four terminal subgraphs, Γ_{2}(2) (≈ K(2, 2)), in the recursive structure.

[figure: 5231; 5213; 5321; 5312; 5132; 5123; 1352; 1325; 1253; 1532; 1523; 1235; 3512; 3251; 3521; 3215; 3152; 3125; 2351; 2135; 2153; 2315; 2531; 2513]

Fig. 2. One subdigraph of Γ_{Δ}(4) isomorphic to Γ_{3}(3).

4 Broadcasting in cycle prefix digraphs

The broadcast algorithm we have designed uses the decomposition into subdigraphs of Γ_{Δ}(D) given in Section 3. The first phase of the algorithm distributes the message from the initial vertex to \binom{Δ+1}{D}−1 other vertices, each in a different subdigraph of the decomposition. In phase two, the message is sent within each subdigraph. The two phases are recursively executed, in parallel, in each subdigraph.

The main point is to build a structure in Γ_{Δ}(D) containing a set of vertices such that any two vertices of the set differ in at least one symbol. This set will have \binom{Δ+1}{D} elements. With this set it is possible to construct a tree to be used in the first phase of the broadcast scheme.

Lemma 2 For any cycle prefix digraph Γ_{Δ}(D) with Δ ≥ D, and any vertex x, there exists a tree T rooted at x with \binom{Δ+1}{D} vertices, depth D, and maximum degree Δ + 1 − D, such that any two vertices in T differ in at least one symbol.

PROOF. We give a constructive proof. Without loss of generality, we may choose x = 12 ⋯ D as the root of T . The successive adjacencies are always of type shift as follows:

Level 1: x is adjacent to the Δ + 1 − D vertices x_{s_{1}}^{1} = 23 ⋯ Ds_{1}, D + 1 ≤ s_{1} ≤ Δ + 1. The upper index of x_{s_{1}}^{1} corresponds to the level and the lower index is the last symbol of the vertex.

Level 2: Vertices at this level are denoted x_{s_{1}s_{2}}^{2} = 3 ⋯ Ds_{1}s_{2}. They are adjacent from x_{s_{1}}^{1} and s_{2} is 1 or is a symbol from {D + 1, …, Δ, Δ + 1} \ {s_{1}} such that s_{2} > s_{1}. At this level there are:

– Δ + 1 − D vertices which end with 1.

– \binom{Δ+1−D}{2} other vertices.

The total number of vertices at level two is Δ + 1 − D+\binom{Δ+1−D}{2} = \binom{Δ+2−D}{2}. Level 3: Vertices x_{s_{1}s_{2}s_{3}}^{3} = 4 … Ds_{1}s_{2}s_{3} are adjacent from x_{s_{1}s_{2}}^{2} by shifts that

add s_{3}, which is 2 or a symbol from {D + 1, …, Δ, Δ + 1} \ {s_{1}, s_{2}} such that s_{1} < s_{2} < s_{3} or s_{1} < s_{3} (if s_{2} = 1). There are:

– \binom{Δ+2−D}{2} vertices with s_{3} = 2.

– \binom{Δ+1−D}{2} vertices with s_{2} = 1 and s_{1} < s_{3}.

– \binom{Δ+1−D}{3} vertices with s_{1} < s_{2} < s_{3} :

The total number of vertices at this level is \binom{Δ+2−D}{2}+\binom{Δ+1−D}{2}+\binom{Δ+1−D}{3} =

\binom{Δ+3−D}{3}. ⋯ Level k: Vertices are x_{s_{1}s_{2}...s_{k}}^{k} = (k + 1) ⋯ Ds_{1}s_{2} ⋯ s_{k} and they are adjacent

from vertices x_{s_{1}s_{2}...s_{k−1}}^{k−1} at level k − 1. s_{k} is either k − 1 or a symbol from {D + 1, …, Δ, Δ + 1} \ {s_{1}, s_{2}, …, s_{k−1}}. All symbols s_{1}, s_{2}, …, s_{k} satisfy the inequality s_{l} < s_{m} if l < m and s_{l} ≠ l − 1 and s_{m} ≠ m − 1. There are:

– \binom{Δ+(k−1)−D}{k−1} vertices with s_{k} = k − 1.

– \binom{Δ+1−D}{k} vertices with D + 1 ≤ s_{1} < … < s_{k} ≤ Δ + 1.

– \binom{Δ+1−D}{k−1} vertices with D + 1 ≤ s_{1} < … < s_{i−1} < s_{i+1} < … < s_{k} ≤ Δ + 1 and s_{i} = i − 1.

– \binom{Δ+1−D}{k−2} vertices with D + 1 ≤ s_{1} < … s_{i−1} < s_{i+1} … s_{j−1} < s_{j+1} < … <

s_{k} ≤ Δ + 1 and s_{i} = i − 1 and s_{j} = j − 1 (i ≠ j).

⋯

– \binom{Δ+1−D}{1} vertices with s_{i} = i − 1 for i = 2 … k.

The total at level k is \binom{Δ+(k−1)−D}{k−1} + ∑_{j=1}^{k−1} \binom{Δ+1−D}{j} = \binom{Δ+k−D}{k} ⋯ Level D: Vertices are x_{s_{1}s_{2}...s_{D}}^{D} = s_{1}s_{2} ⋯ s_{D} and they are adjacent from ver-

tices at level D−1, x_{s_{1}s_{2}...s_{D−1}}^{D−1} and s_{D} is such that s_{1} < s_{2} < … < s_{D−1} < s_{D} except when s_{j} = j − 1, j = 2 … D − 1. The process finishes at this level and a similar count than in level k gives \binom{Δ}{D} vertices.

Therefore the maximum degree of T is Δ + 1 − D, its depth is D and T has ∑_{k=0}^{D} \binom{Δ+k−D}{k} = \binom{Δ+1}{D} vertices. This is precisely the number of choices of D different elements from an alphabet of Δ + 1 symbols.

It is not difficult to see that any two vertices in T differ in at least one symbol. First, notice that any vertex at level k of the tree has the form x = (k + 1) ⋯ Ds_{1}s_{2} ⋯ s_{k} (x = s_{1}s_{2} ⋯ s_{D}, if k = D) with s_{i} < s_{j} if i < j and s_{i} ≠ i − 1 and s_{j} ≠ j − 1. The symbol k is not contained in any of the vertices of level k. Let x = (p + 1) ⋯ Ds_{1}s_{2} ⋯ s_{p} and x′ = (q + 1) ⋯ Ds′_{1}s′_{2} ⋯ s′_{q} be two different vertices of T not at level D. If p ≠ q, say p < q, then x = (p + 1) ⋯ q(q + 1) ⋯ Ds_{1}s_{2} ⋯ s_{p}, but as q is not a symbol of x′, the vertices differ at least in this symbol. If one of the vertices is at level D it will not contain the symbol D, but as all other vertices contain it, the two vertices will differ at least in that symbol. On the other hand, if the vertices are both at the same level, in order to differ at least in one symbol {s_{1}, ⋯, s_{p}} should be a different set of symbols than {s′_{1}, ⋯, s′_{p}}, (p ≤ D) . Let us suppose that s_{1} ≠ s′_{1} and s_{1} < s′_{1}, then, because of the construction s_{1} ∉ {s′_{1}, …, s′_{p}} and both vertices will not share the same set of symbols. Otherwise, let i, 1 < i ≤ p be the first position for which s_{i} ≠ s′_{i}, if s_{i} = i − 1 (or s′_{i} = i − 1) then symbol s_{i} is not in x′ (or s′_{i} is not in x). Therefore s_{i} < s′_{i} and in this case s_{i} will not be in x′ because after position i, the construction only allows to add symbols s′ such that s′ > s′_{i}. □

Remark 3 If Δ = D, instead of a tree we have a path of length D.

Example 4 The tree associated with Γ_{5}(4) has depth D = 4, maximum degree Δ + 1 − D = 2, and contains \binom{Δ+1}{D} = \binom{6}{4} = 15 vertices. The tree is shown in Figure 3.

From the proof of the preceeding lemma, the vertices of level one are obtained by shifts that add one of the symbols {5, 6} to the end of the root 1234. These vertices are 2345 and 2346

At level two there is one vertex ending with 1 adjacent from each of the vertices

[figure: 5123 (4); 5126 (5); 5163 (5); 5623 (5); 6123 (5); Level 4; 4512 (3); 4516 (4); 4562 (4); 4612 (4); Level 3; 3451 (2); 3456 (3); 3461 (3); Level 2; 2345 (1); 2346 (2); Level 1; 1234 (0)]

Fig. 3. The basic tree for Γ_{5}(4). Boldface numbers indicate the broadcast order using the scheme of Theorem 5.

of level one (3451, 3461). The other vertex of this level must be 34s_{1}s_{2} with s_{1} < s_{2} and s_{1}, s_{2} ∈ {5, 6}. The only possible choice for s_{1} and s_{2} gives 3456 which is adjacent from 2345.

We obtain three vertices of level three (4512, 4562, 4612) from vertices of level two by shifts that add 2. The other vertices of this level must end with one of the symbols in {D + 1, …, Δ, Δ + 1} \ {s_{1}, s_{2}} = {5, 6} \ {s_{1}, s_{2}}. Therefore, vertex 4s_{1}s_{2}s_{3} must be such that s_{1} ∈ {5, 6} and when s_{2} = 1 the condition s_{1} < s_{3} leads to the choice s_{1} = 5, s_{3} = 6, giving vertex 4516. When s_{2} ≠ 1 it is not possible to give symbols satisfying s_{1} < s_{2} < s_{3}.

The vertices of the last level start with a symbol from {D + 1, …, Δ + 1} = {5, 6}. Four vertices will end with 3 and are adjacent from each vertex of level 3, (5123, 5163, 5623, 6123). The other vertex, following arguments similar to those for level three, is 5126.

Theorem 5 The broadcast time for Γ_{Δ}(D), Δ ≥ D, is bounded as follows.

b(Γ_{Δ}(D)) ≤ Δ + \frac{D(D − 1)}{2}

PROOF. We start the broadcast process using the tree constructed according to Lemma 2. The originator sends the message to its adjacent vertices in lexicographic order. Any vertex in the tree proceeds in the same way, as shown in Figure 3. Therefore, to broadcast a message from the origin to all vertices of the tree takes Δ time units.

From each vertex of the tree the message is then broadcast to a subdigraph (isomorphic to Γ_{D−1}(D − 1)). To broadcast in this digraph, we will follow the same scheme but now instead of a tree we have a path (Remark 3). The process is recursively repeated for each new vertex reached. We denote by β(Γ_{k}(k)) the time that this broadcasting scheme takes to broadcast in Γ_{k}(k). As the broadcasting process first uses a path P_{k} of length k we have the following expression:

β(Γ_{k}(k)) = b(P_{k}) + β(Γ_{k−1}(k − 1)) k > 3

Using this recurrence relation, and the facts that b(P_{k}) = k and β(Γ_{2}(2)) = b(K(2, 2)) = 3, we obtain:

β(Γ_{k}(k)) = b(P_{k}) + b(P_{k−1}) + ⋯ + b(P_{3}) + β(Γ_{2}(2))
= k + (k − 1) + ⋯ + 3 + 3 = \frac{k(k + 1)}{2}

Combining the results, the broadcasting time of a cycle prefix digraph is:

b(Γ_{Δ}(D)) ≤ b(T ) + β(Γ_{D−1}(D − 1)) = Δ + \frac{D(D − 1)}{2} □

5 Conclusions

In this paper we have presented a recursive decomposition of the cycle prefix digraph that yields an efficient broadcasting scheme.

It is interesting to compare the broadcast times that result from this scheme with those known for other digraphs with similar order for the same degree and diameter. In [1] Bermond and Peyrat give b(B(Δ, D) ≤ \frac{(Δ+1)(D+1)}{2}, 2 ≤ D ≤ 14, as the smallest upper bound on the broadcast time of de Bruijn digraphs. Our scheme leads to much better broasdcast times for comparable cycle prefix digraphs (see Table 1).

Table 1

Γ_{Δ}(3)  B(Δ, 3)

Δ |V | β(Γ_{Δ}(3)) |V | β′(B(Δ, (3))

3 24  6  27  8 4 60  7  64  10 5 120  8 125  12 6 210  9 216  14 7 336  10 343  16 8 504  11 512  18 9 720  12 729  20 10 990  13 1000  22 Comparative values of the broadcast time of cycle prefix digraphs, β(Γ_{Δ}(3)), and de Bruijn digraphs of diameter three, β′(B(Δ, 3)), for small values of the degree.

On the other hand, Γ_{Δ}(2) is the Kautz digraphs K(Δ, 2). Heydemann, Opatrny and Sotteau [9] give the best known upper bounds on the broadcast time of Kautz digraphs as:

b(K(2, D)) ≤ 2D,
b(K(3, D)) ≤ 3D,
b(K(Δ, D)) ≤ \{ \begin{matrix}\frac{(Δ+3)(D+1)}{2}, & if 4 ≤ Δ ≤ 12, Δ ≠ 9 \\ min\{2D⌈log_{2} Δ⌉, 3D⌈log_{3} Δ⌉\}, & if Δ = 9 or Δ ≥ 13 \end{matrix}

For D = 2 and small degrees, Theorem 5 improves these results giving a new upper bound of β(K(Δ, 2)) = Δ + 1. This broadcasting time is optimal for small values of the degree (Δ < 6).

Finally, we mention that it should be possible to further exploit the hierarchical nature of the cycle prefix digraphs to deal with other communication problems.

References

[1] J.C. Bermond and C. Peyrat, Broadcasting in de Bruijn networks, Congressus Numerantium, 66 (1988) 283–292.

[2] P. Berthomé, A. Ferreira, and S. Perennes, Optimal information dissemination in Star and Pancake networks. Tech. Rept., LIP (ENS-Lyon, 1992).

[3] W.Y.C. Chen, V. Faber, and E. Knill, Restricted routing and wide diameter of the cycle prefix network, Tech. Rept. LACES-94C-94-5 (Los Alamos National Laboratory, Los Alamos, NM, 1994).

[4] F. Comellas and M.A. Fiol, Vertex symmetric digraphs with small diameter, Discrete Appl. Math. 58 (1995) 1–11.

[5] V. Faber and J.W. Moore, High-degree low-diameter interconnection networks with vertex symmetry: directed case, Tech. Rept. LA-UR-88-1051 (Los Alamos National Laboratory, Los Alamos, NM, 1988).

[6] V. Faber, J.W. Moore, and W.Y.C. Chen, Cycle prefix digraphs for symmetric interconnection networks, Networks 23 (1993) 641–649.

[7] C. GowriSankaran, Broadcasting on recursively decomposable Cayley graphs, Discrete Appl. Math. 53 (1994) 171–182.

[8] Y.O. Hamidoune, A.S. Lladó, and O. Serra, The connectivity of hierarchical Cayley digraphs, Discrete Appl. Math. 37/38 (1992) 275–280.

[9] M.C. Heydemann, J. Opatrny, and D. Sotteau, Broadcasting and spanning trees in de Bruijn and Kautz networks, Discrete Appl. Math. 37/38 (1992) 297–317.

[10] D.F. Hsu, On container width and length in graphs, groups and networks, IEICE Trans. Fundamentals E77-A (1994) 668–680.

[11] M. Jiang and K. Ruskey. Determining the Hamilton-connectedness of certain vertex transitive graphs. Discrete Math. 133 (1994) 159–170.

[12] E. Knill, Notes on the connectivity of Cayley coset digraphs, Tech. Rept. LAUR-94-3719 05C-94-30 (Los Alamos National Laboratory, Los Alamos, NM, 1994).

[13] G. Sabidussi, Vertex transitive graphs, Monatsh. Math. 68 (1969) 426–438.