Cycles in the cycle prefix digraph

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

aDepartament de Matemàtica Aplicada i Telemàtica, UPC Campus Nord, C3, 08034 Barcelona, Catalonia, Spain. bDepartament de Matemàtica Aplicada I, UPC c/ Gregorio Marañón 44, 08028 Barcelona, Catalonia, Spain

Abstract

Cycle prefix digraphs are a class of Cayley coset graphs with many remarkable properties such as symmetry, large number of nodes for a given degree and diameter, simple shortest path routing, Hamiltonicity, optimal connectivity, and others. In this paper we show that the cycle prefix digraphs, like the Kautz digraphs, contain cycles of all lengths l, with l between two and N, the order of the digraph, except for N − 1.

Ars Combinatoria 60, pp. 171–180 (2001).

1 Introduction

Several families of digraphs have been proposed as a model for directed interconnection networks for parallel architectures, distributed computing and communication networks [6, 2]. One of these is the family of Kautz digraphs that have been extensively studied in the literature. In particular, Villar (see [10]) showed that Kautz digraphs are almost pancyclic and contain cycles of any length between two and N, the order of the digraph, except for N − 1. Cycle prefix digraphs constitute a family of Cayley coset digraphs which is particularly attractive. For diameter two, the cycle prefix digraphs and the Kautz digraphs are isomorphic. In general they have many properties that make them an interesting alternative to the Kautz digraphs. Firstly, the cycle prefix digraphs are vertex symmetric, or arc transitive, and therefore in the associated network each node is able to execute the same communication software. These digraphs are also specially significant for the construction of networks with order as large as possible for a given maximum degree and diameter. They form, together with other families constructed from them [2], most of the entries of the table of largest known vertex symmetric digraphs^{1}. Other remarkable properties are: Hamiltonicity [8], simple shortest path routing, and optimal connectivity [9]. The wide diameter of a cycle prefix digraph with diameter D is D +2 [1] (the wide diameter of a graph is considered an important measure of communication efficiency and reliability, see [7]). For D ≥ 3, the digraphs are D−reachable and a message sent from any vertex may reach all other vertices (including the originator) in exactly D steps [2]. Other aspects of interest are their modularity and simple definition. A broadcasting algorithm based on their hierarchical structure was given in [3].

In this paper we are interested in the existence of cycles of all lenghts in these digraphs. This knowledge will help in designing good communication strategies for the corresponding networks. In the next section we will introduce the notation and give some known results and in Section 3, given a cycle prefix digraph of order |V |, we obtain cycles of any length l, for l = 2 … |V |, except when l = |V | − 1.

2 Cycle prefix digraphs. Notation and previous results.

Γ_{Δ}(D) will denote a cycle prefix digraph of degree Δ and diameter D. These digraphs were introduced as Cayley coset digraphs by Faber and Moore in 1988 [4, 5] and they may also be defined on an alphabet of Δ + 1 symbols 0, 1, …, Δ as follows: 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_{2}x_{3}x_{4} ⋯ x_{D}x_{1} \\ x_{1}x_{2} ⋯ x_{k−1}x_{k+1} ⋯ x_{D}x_{k}, & 2 ≤ 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: r_{k} is the adjacency rotating the symbol in position k to the end of the word. Through this paper ⇒ will denote the adjacency r_{1}.

Γ_{Δ}(D) is a vertex symmetric digraph that has order (Δ+1)_{D} = \frac{(Δ+1)!}{(Δ+1−D)!}, diameter D and is Δ-regular (Δ ≥ D). The digraph has a hierarchical structure and may be decomposed into \binom{Δ+1}{D} subdigraphs isomorphic to Γ_{D−1}(D − 1), with D ≥ 3, see [3]. Shift adjacencies connect different subdigraphs whereas rotations join vertices in the same subdigraph.

Cycle prefix digraphs are Hamiltonian, see [8]. Another result that we will use from the paper of Jiang and Ruskey [8] is the existence in Γ_{D}(D) of a Hamiltonian path in each subdigraph isomorphic to Γ_{D−1}(D − 1) that contains D adjacencies of type r_{1} such that first symbols are different from one to another.

1An up-to-date table of the largest known vertex symmetric digraphs is maintained at http://www-mat.upc.es/grup de grafs/grafs/taula vsd.html

Finally, we will also use in this paper the fact that an adjacency r_{1}, connects two vertices such that the first symbol of the first vertex is equal to the last symbol of the second vertex, i.e. x_{1} … x_{D} ⇒ x_{2} … x_{D}x_{1}.

3 Cycles in Γ_{Δ}(D)

In this section we obtain for the cycle prefix digraph of degree Δ and diameter D (Δ ≥ D) Γ_{Δ}(D) = G(V, E) cycles of any length |V |, for N = 2 … |V |, except when N = |V |−1. We will distinguish between short cycles (with length less than or equal to D + 1) and long cycles.

3.1 Short cycles.

We show in the following theorem that each vertex x in Γ_{Δ}(D), Δ ≥ D, belongs to a cycle C_{k}(x) of length k, 2 ≤ k ≤ D. Cycles C_{k}(x) are vertex– disjoint, except for x.

Theorem 1 Let Γ_{Δ}(D), Δ ≥ D, be the cycle prefix digraph of degree Δ and diameter D and let x = x_{1}x_{2}..x_{D} be a vertex in Γ_{Δ}(D).Then x belongs to a family of cycles C_{k}(x), where C_{k}(x) has length k, 2 ≤ k ≤ D, and

⋂_{k=2}^{D} C_{k}(x) = {x}.

Proof. The cycle C_{k}(x) is obtained by successively applying the rotation r_{D−(k−1)} to x.

Remark 1 All D adjacencies of the cycle C_{D} are of type r_{1}.

Example 1 In Γ_{7}(5), the cycles C_{k}(x) for a vertex x = 63412 are:

C_{2}(x) : 63412 → 63421 → 63412
C_{3}(x) : 63412 → 63124 → 63241 → 63412
C_{4}(x) : 63412 → 64123 → 61234 → 62341 → 63412
C_{5}(x) : 63412 → 34126 → 41263 → 12634 → 26341 → 63412

The next theorem allows the construction of cycles of length D + 1. We show that each vertex x in Γ_{Δ}(D), Δ ≥ D, may be included in Δ + 1 − D different cycles of this length where the adjacencies are all of type shift. We will call this cycles shift cycles.

Theorem 2 Given Γ_{Δ}(D), Δ ≥ D and a vertex x = x_{1}x_{2}..x_{D} then x is in Δ + 1 − D cycles, C_{y}(x), of length D + 1 and ⋂_{y≠x_{1},...,x_{D}} C_{y}(x) = {x}.

Proof.

C_{y} : x = x_{1}x_{2}..x_{D} → x_{2}..x_{D}y → x_{3}..x_{D}yx_{1} … → yx_{1}..x_{D−1} → x_{1}x_{2}..x_{D}

Since in each cycle C_{y}, the symbol y is different, all the cycles have only x as a common vertex. The number of cycles of length D +1 is the number of choices of y ≠ x_{1}, …, x_{D} from the alphabet of Δ + 1 symbols: Δ + 1 − D.

3.2 Long cycles.

We begin the construction of cycles of length k, k > D + 1 by studying the cases D = 2 and D = 3. We use then the recursive structure of the cycle prefix digraphs to generalize the results to the case Γ_{Δ}(D), Δ ≥ D.

Since digraphs Γ_{Δ}(D) are vertex symmetric, without loss of generality we may consider the identity vertex I = 12 … D as the starting vertex of a cycle.

Γ_{2}(2)

Cycles containing I = 12 are:

C_{2} 12 21
C_{3} 12 23 31
C_{4} 12 21 13 31
C_{6} 12 21 13 32 23 31

The cycle C_{5} does not exist.

Γ_{3}(3)

Remark 2 Any arc in Γ_{Δ}(3) of type r_{1}, say, xyz ⇒ yzx, can be replaced by a path with 3, 4 or 6 vertices . These vertices have symbols {y, z, t} with t ≠ x, therefore they are in the same subdigraph and the paths are isomorphic, respectively, to C_{3}, C_{4} and C_{6} in the former case, see Figure 1. For example, the arc 123 ⇒ 231 can be replaced with vertices that contain the symbols {2, 3, 4}:

123 ⇒ 231 : 123 \{ \begin{matrix}234 & 342 & 423 \\ 234 & 243 & 432 & 423 \\ 234 & 243 & 432 & 324 & 342 & 423 \end{matrix} \} 231

• Cycles of length 5. It is not possible to obtain a cycle of length 5 with all the vertices in the same subdigraph (isomorphic to Γ_{2}(2)),

[figure: 20; 02; 21; 10; 12; 01; 312; 321; 213; 132; 231; 123]

Figure 1: The digraph Γ_{2}(2) and one subdigraph of Γ_{Δ}(3) isomorphic to it.

i.e. vertices with symbols {1, 2, 3}. We show here several possible cycles of length 5. Notice that in all of them there is always an adjacency of type r_{1}:

123 → 234 ⇒ 342 → 421 → 412
123 → 234 → 341 ⇒ 413 → 132
123 ⇒ 231 → 314 → 341 → 412

• Cycles of length 6. The Hamiltonian cycles of each subdigraph Γ_{2}(2) have length 6.

• Cycles of length 7. They may be constructed from any cycle of length 3, C_{3}, by replacing one arc with a path of four vertices. This substitution is always possible because all the adjacencies are of type r_{1}. From C_{3}(I) : 123 ⇒ 231 ⇒ 312 we obtain

123 → 234 → 243 ⇒ 432 → 423 → 231 ⇒ 312

• Cycles of length 8. Notice that there is always an adjacency of type r_{1} in the cycles of length 5 listed above which can be replaced by a path of three vertices to obtain a cycle of length 8:

123 → 234 → 341 ⇒ 413 ⇒ 134 → 342 → 421 → 412

• Cycle of length 11. It may be constructed from any cycle of length 3 by replacing two arcs with paths of four vertices and one arc with a path of three vertices.

• Cycles of length 9, 10, 12, … 22, 24. Γ_{3}(3) contains four subdigraphs isomorphic to Γ_{2}(2). In each Γ_{2}(2), as was stated in Section 2, there is a Hamiltonian cycle containing three adjacencies of type r_{1}. Following the substitution process of Remark 2, we have cycles of lengths 9, 10, 12 … 22 and 24 vertices. see Figure 2.

[figure: 123; 132; 321; 213; 231; 312; 324; 342; 432; 423; 234; 243]

Figure 2: An Hamiltonian cycle in Γ_{2}(2) and the substitution of each arc r_{1} by paths of three, four or six vertices.

In general, to obtain a cycle of length k (k ≠ 5, 7, 8, 11) we write k = 6(1 + q) + r with 0 ≤ q ≤ 3 and 0 ≤ r < 6. We consider a Hamiltonian cycle in one of the subdigraphs isomorphic to Γ_{2}(2). This cycle has three arcs of type r_{1} that may be replaced by a path with three, four or six vertices, then:

• If r = 0, 3, 4. Replace q adjacencies r_{1} by q Hamiltonian paths and a different adjacency r_{1} by a path with r vertices.

• If r = 1, 2 then 1 ≤ q < 3. Replace q − 1 adjacencies r_{1} with Hamiltonian paths, use the remaining adjacencies r_{1} to complete 6+r vertices.

• If r = 5 then 1 ≤ q < 3. Replace q−1 adjacencies r_{1} with Hamiltonian paths. We need three more adjacencies to complete the 11 remaining vertices with two paths of length 4 and one path of length 3. This process is only possible if q ≠ 2 and, consequently, k ≠ 23.

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

We recall that Γ_{Δ}(3) contains \binom{Δ+1}{3} subdigraphs isomorphic to Γ_{2}(2), and that the order of the digraph is |Γ_{Δ}(3)| = (Δ + 1)_{3} = 6\binom{Δ+1}{3} = |Γ_{2}(2)|\binom{Δ+1}{3}.

Next we introduce the substitution tree T of Γ_{Δ}(D), see Figure 3. This tree will be used to select pairs of cycles in different subdigraphs with vertices differing only in one symbol. The cycles may be joined to obtain new longer cycles.

Each node of this tree is a subset of D symbols used in Γ_{Δ}(D) and the tree is made as follows. We choose the vertex I = 12 … D as root of T . At the first level we replace each one of the symbols 1, 2 … D by D + 1, at the second level we replace each symbol in a node of the first level by D +2 and so on. Boldface numbers in Figure 3 indicate the replaced symbol. After this process, we obtain a tree with depth Δ + 1 − D, maximum degree D and such that a new symbol is introduced at each level. Notice that the branches of T are not directly related to the arcs of Γ_{Δ}(D). To obtain a

[figure: (5) {1, 2, 6}; (5) {1, 3, 6}; (5) {1, 4, 6}; (4) {1, 5, 6}; (5) {2, 3, 6}; (5) {2, 4, 6}; (4) {2, 5, 6}; (5) {3, 4, 6}; (4) {3, 5, 6}; (3) {4, 5, 6}; (4) {1, 2, 5}; (4) {1, 3, 5}; (3) {1, 4, 5}; (4) {2, 3, 5}; (3) {2, 4, 5}; (2) {3, 4, 5}; (3) {1, 2, 4}; (2) {1, 3, 4}; (1) {2, 3, 4}; {1, 2, 3}]

Figure 3: The substitution tree T of Γ_{5}(3)

cycle of length k, k ≥ 23, we start by writing the cycle with symbols {1, 2, 3} (associated to the root of T ), which is isomorphic to the Hamiltonian path in Γ_{2}(2). We can replace the three adjacencies r_{1} of this cycle by paths using the symbols {2, 3, 4}, {1, 3, 4} and {1, 2, 4} respectively and obtain in this way, cycles of lengths k = 9, … 22 and 24. Next we will replace the three adjacencies r_{1} in the Hamiltonian path with symbols {2, 3, 4} by paths using {3, 4, 5}, {2, 4, 5} and {2, 3, 5}. Then we will replace two adjacencies r_{1} in the Hamiltonian path which has symbols {1, 3, 4} by paths on {1, 4, 5} and {1, 3, 5}. Finally we replace one adjacency r_{1} in the Hamiltonian path with symbols {1, 2, 4} by paths using {1, 2, 5}. A new symbol, 6, is introduced here following the scheme given by T .

Notice that in Γ_{Δ}(3), because of the Hamiltonian path in Γ_{2}(2), there are \binom{Δ+1}{3} − 1 adjacencies of type r_{1} that may be replaced.

To obtain a cycle of length k in Γ_{Δ}(3) , we write k = 6(1 + q) + r, q ≤ \binom{Δ+1}{3} − 1 and r < 6, and we distinguish the following cases:

• Case r = 0, 3, 4. We construct q Hamiltonian paths on the Hamiltonian cycle with symbols {1, 2, 3}, and we replace one of the remaining arcs r_{1} by a path of length r.

• Case r = 1, 2. Notice that q < \binom{Δ+1}{3} − 1. We construct q − 1 Hamiltonian paths on the Hamiltonian cycle with symbols {1, 2, 3},

[figure]

Figure 4: An schematic description of the procedure to substitute adjacencies r_{1} in a Hamiltonian cycle of a subdigraph Γ_{2}(2)

and we replace two of the remaining arcs r_{1} by two paths of total length 6 + r.

• Case r = 5. We construct in this case q−1 Hamiltonian paths and we replace the three remaining arcs r_{1} by two paths of total length 11 = 4+4+3. This is always possible except when (\binom{Δ+1}{3}−1)−(q−1) = 2, that is, when k = 6\binom{Δ+1}{3} − 1 = |Γ_{Δ}(3)| − 1.

The main result of this paper is summarized by the following theorem:

Theorem 3 The cycle prefix digraph Γ_{Δ}(D), Δ ≥ D, contains cycles of any length k, 2 ≤ k ≤ |Γ_{Δ}(D)|, except when k = |Γ_{Δ}(D)| − 1.

Proof. Theorems 1 and 2 ensure the existence of cycles of length 2 to D + 1 in Γ_{Δ}(D). To prove the existence of longer cycles we will proceed by induction over D. The assertion holds when D = 3.

Suppose that there exists a cycle of length k, 2 < k ≤ |Γ_{Δ}(D − 1)|, k ≠ |Γ_{Δ}(D − 1)| − 1 in Γ_{Δ}(D − 1). We need to construct paths of length k = |Γ_{Δ}(D − 1)| − 1 and |Γ_{Δ}(D − 1)| < k ≤ |Γ_{Δ}(D)|, k ≠ |Γ_{Δ}(D)| − 1, in Γ_{Δ}(D).

• Case k = |Γ_{D−1}(D − 1)| − 1. The path

12 … D → 23 … D(D + 1) ⇒ 3 … D(D + 1)2 →

4 … D(D + 1)21 → 4 … D(D + 1)12 → … → (D + 1)12 … (D − 1)

has D + 2 vertices and one adjacency of type r_{1} which can be replaced by a path with |Γ_{D−1}(D − 1)| − D − 3 vertices and symbols {1, 3 … D, (D +1)}, to obtain a path with |Γ_{D−1}(D −1)|−1 vertices.

• Case |Γ_{D−1}(D − 1)| < k ≤ |Γ_{Δ}(D)| and k ≠ |Γ_{Δ}(D)| − 1. We start with a Hamiltonian path in one of the subdigraphs isomorphic to Γ_{D−1}(D − 1)

12 … D → … → D1 … (D − 1)

The results obtained by Jiang and Ruskey [8] and quoted at the end od Section 2, ensure that this path has D adjacencies r_{1} which can be replaced following the scheme given by the corresponding substitution tree T . Overall there are \binom{Δ+1}{D} − 1 adjacencies r_{1} to replace. Moreover |Γ_{Δ}(D)| = |Γ_{D−1}(D − 1)|\binom{Δ+1}{D}. To obtain the cycle of length k, we write k = |Γ_{D−1}(D − 1)|(q + 1) + r, with q ≤ \binom{Δ+1}{D} − 1, r < |Γ_{D−1}(D − 1)|, and we consider the following cases:

– Case r = 0, D, D + 1 … |Γ_{D−1}(D − 1)| − 2. Replace q adjacencies r_{1} by Hamiltonian paths in q different copies of Γ_{D−1}(D−1) and use a remaining adjacency r_{1} to replace it with r vertices.

– Case r = 1, 2, … D − 1. In this case q < \binom{Δ+1}{D} − 1. Replace q − 1 adjacencies r_{1} by Hamiltonian paths in q − 1 different copies of Γ_{D−1}(D − 1) and use two remaining adjacencies r_{1} to replace them with |Γ_{D−1}(D − 1)| + r vertices. This can always be done because |Γ_{D−1}(D − 1)| + r = a + b with D < a, b < |Γ_{D−1}(D − 1)| − 1 and there are always two arcs to replace: \binom{Δ+1}{D} − 1 − (q − 1) ≥ 2.

– Case r = |Γ_{D−1}(D − 1)| − 1. Replace q − 1 adjacencies r_{1} by Hamiltonian paths. We need to add 2|Γ_{D−1}(D −1)|−1 vertices. We must use three of the remaining adjacencies r_{1} to ensure that each adjacency is replaced by less than |Γ_{D−1}(D − 1)| − 1 vertices. This process can be done when \binom{Δ+1}{D}−1−(q −1) ≥ 3.

When \binom{Δ+1}{D} − 1 − (q − 1) = 2 then q = \binom{Δ+1}{D} − 2 and it is not possible to have a cycle of length

k = |Γ_{D−1}(D − 1)|\binom{Δ + 1}{D} − 1 = |Γ_{Δ}(D)| − 1

4 Conclusions

In this paper we have studied the cycle structure of cycle prefix digraphs. In particular, for the cycle prefix digraph of degree Δ and diameter D, Δ ≥ D, Γ_{Δ}(D) = G(V, E), we have obtained cycles of any length l, for l = 2 … |V |, except when l = |V | − 1. The existence for Γ_{Δ}(D) = G(V, E) of cycles of length |V | − 1 is an open problem. We have checked that all cycle prefix digraphs with small order (|V | ≤ 720) do not contain a cycle of length |V |−1 and we conjecture that, as it happens for the Kautz digraphs, these digraphs are almost pancyclic.

Acknowledgement

This work has been supported by the Comisión Interministerial de Ciencia y Tecnología, Spain, under project CICYT-TIC97-0963.

References

[1] W.Y.C. Chen, V. Faber, and E. Knill, Restricted routing and wide diameter of the cycle prefix network, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Interconnection Networks and Mapping and Scheduling Parallel Computations, Eds. D. Sotteau, D.F. Hsu and A.L. Rosenberg, v.2 (1995) 31–46.

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

[3] F. Comellas and M. Mitjana. Broadcasting in cycle prefix digraphs. Discrete Appl. Math., 83 (1998) 31–39.

[4] 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).

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

[6] M.J. Dinneen, and P. Hafner, New results for the degree/diameter problem. Networks, 24 (1994) 359–367.

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

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

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

[10] J. Villar, Kautz S-ary closed sequences, Combinatorics’88. Proceedings of the International Conference on Incidence Geometries and Combinatorial Structures. 2nd Vol. , (1991) 459–469.