From subKautz digraphs to cyclic Kautz digraphs

From subKautz digraphs to cyclic Kautz digraphs ∗ C. Dalf´o Departament de Matem`atiques Universitat Polit`ecnica de Catalunya Barcelona, Catalonia [email protected] Abstract Kautz digraphs K(d, `) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz digraphs CK(d, `) were recently introduced by B¨ohmov´a, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to cyclic Kautz digraphs by introducing the family of subKautz digraphs sK(d, `), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, `) and CK(d, `). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, `) and CK(d, `) are maximally vertex-connected and super-edge-connected. Whereas K(d, `) are optimal with respect to the diameter, we show that sK(d, `) and CK(d, `) are optimal with respect to the mean distance, whose exact values are given for both families when `= 3. Finally, we provide a lower bound on the girth of CK(d, `) and sK(d, `). Mathematics Subject Classifications: 05C20, 05C50. Keywords: Digraph, distance, diameter, mean distance, routing, Kautz digraph, line digraph, vertex- and edge-connectivity, superconnectivity, semigirth, girth. ∗This research is supported by MINECO under project MTM2014-60127-P, and the Catalan Research Council under project 2014SGR1147. This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. 1 2 1 Introduction Originally, Kautz digraphs were introduced by Kautz [9] in 1968. They have many applications, for example, they are useful as network topologies for connecting processors. Kautz digraphs have the smallest diameter among all digraphs with their number of vertices and degree. The cyclic Kautz digraphs CK(d, `) were recently introduced by B¨ohmov´a, Huemer and the author [2, 3], as subdigraphs with special symmetries of the well-known Kautz digraphs CK(d, `), see for example Fiol, Yebra and Alegre [7]. In contrast with these, the set of vertices of the cyclic Kautz digraphs is invariant under cyclic permutations of the sequences representing them. Thus, apart from their possible applications in interconnection networks, cyclic Kautz digraphs CK(d, `) could be relevant in coding theory, because they are related to cyclic codes. A linear code Cof length `is called cyclic if, for every codeword c= (c1, . . . , c`), the codeword (c`, c1, . . . , c`−1) is also in C. This cyclic permutation allows to identify codewords with polynomials. For more information about cyclic codes and coding theory, see Van Lint [10] (Chapter 6). With respect to other properties of cyclic Kautz digraphs CK(d, `), their number of vertices follows sequences that have several interpretations. For example, for d= 2 (that is, 3 different symbols), the number of vertices follows the sequence 6,6,18,30,66, . . . According to the On-Line Encyclopedia of Integer Sequences [12], this is the sequence A092297. For d= 3 (4 different symbols) and `= 2,3, . . ., we get the sequence 12,24,84,240,732, . . . corresponding to A226493 and A218034 in [12]. In this paper we give an alternative definition of CK(d, `), by introducing the family of subKautz digraphs sK(d, `), from where the cyclic Kautz digraphs can be obtained as line digraphs. We present the exact formula of the distance between any two vertices of sK(d, `) and CK(d, `). This allows us to compute the diameter and the semigirth of both families, also providing an efficient routing algorithm to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, `) and CK(d, `) are maximally vertex-connected and super-edge-connected. Whereas K(d, `) are optimal with respect to the diameter, we show that sK(d, `) and CK(d, `) are optimal with respect to the mean distance, whose exact values are given for both families when `= 3. Finally, we provide a lower bound on the girth of CK(d, `) and sK(d, `). 1.1 Notation We consider simple digraphs (or directed graphs) without loops or multiple arcs, and we follow the usual notation for them, that is, a digraph G= (V, E) consists of a (finite) set V=V(G) of vertices and a set E=E(G) of arcs (directed edges) between vertices of G. If a= (u, v) is an arc between vertices uand v, then vertex uis adjacent to vertex v, and vertex vis adjacent from u. Let Γ+(v) and Γ−(v) denote the set of vertices adjacent from and to vertex v, respectively. Their cardinalities are the out-degree δ+(v) = |Γ+(v)|of 3 vertex v, and the in-degree δ−(v) = |Γ−(v)|of vertex v. For all v∈V, a digraph Gis called d-out-regular if δ+(v) = d,d-in-regular if δ−(v) = d, and d-regular if δ+(v) = δ−(v) = d. The minimum degree δ=δ(G) of Gis the minimum over all the in-degrees and out-degrees of the vertices of G. A digon is a directed cycle on 2 vertices. For other notation, and unless otherwise stated, we follow the book by Bang-Jensen and Gutin [1]. In the line digraph L(G) of a digraph G, each vertex represents an arc of G,V(L(G) = {uv : (u, v)∈E(G)}, and a vertex uv is adjacent to a vertex wz when v=w, that is, when in Gthe arc (u, v) is adjacent to the arc (w, z): u→v(= w)→z. Fiol and Llad´o defined in [6] the partial line digraph P L(G) of a digraph G, where some (but not necessarily all, as in the line digraph L(G)) of the arcs in Gbecome vertices in P L(G). Let E0⊆Ebe a subset of arcs which are adjacent to all vertices of G, that is, {v; (u, v)∈E0}=V. A digraph P L(G) is said to be a partial line digraph of Gif its vertices represent the arcs of E0, that is, V(P L(G)) = {uv; (u, v)∈E0}, and a vertex uv is adjacent to vertices v0w, for each w∈Γ+ G(v), where v0=(vif vw ∈V(P L(G)), any other vertex of Γ− G(w) such that v0w∈V(P L(G)) otherwise. A digraph Gis strongly connected when, for any pair of vertices x, y ∈V, there always exists an x→ypath. The strong connectivity κ=κ(G) (or strong vertex-connectivity) of Gis the smallest number of vertices whose deletion results in a digraph that is either nonstrongly connected or trivial. Analogously, the strong arc-connectivity λ=λ(G) of G is the smallest number of arcs whose deletion results in a nonstrongly connected digraph. Since we only deal with strong connectivities, from now on we are going to refer to them simply as connectivities. Now we only consider connected digraphs, so δ≥1. It is known that κ≤λ≤δ, see Geller and Harary [8]. A digraph Gis maximally connected when κ=λ=δ. If Gis a maximally arc-connected digraph (λ=δ), then any set of arcs adjacent from [to] a vertex xwith out-degree [in-degree] δis a minimum order arc-disconnecting set. Similarly, if Gis a maximally vertex-connected digraph (κ=δ), the set of vertices adjacent from [to] xis a minimum order vertex-disconnecting set. In this context, these arc or vertex sets are called trivial. Note that the deletion of any trivial set isolates a vertex of in-degree or out-degree δ. A digraph Gis super-κif every minimum arc-disconnecting set is trivial. Analogously, Gis super-λis all its minimum vertex-disconnecting sets are trivial. If Gis super-κ, then κ=δ, and if Gis super-λ, then λ=δ. In general, the converses are not true. We say that a digraph is weakly antipodal when every vertex uhas exactly one vertex vat maximum distance (the diameter), and it is antipodal when simultaneously uand v are at maximum distance from each other. For instance, the directed cycle Cnis weakly antipodal, whereas the symmetric directed cycle C∗ nwith even nis antipodal. 4 1.2 The semigirth or parameter l We recall the definition of the semigirth (or parameter l): For a given digraph G, let l=l(G), for 1 ≤l≤D, be the greatest integer such that for any two (not necessarily different) vertices x, y ∈V, (a) if dist(x, y)< l, then the shortest x→ypath is unique, and there is no an x→y path of length dist(x, y) + 1; (b) if dist(x, y) = l, then there is only one shortest x→ypath. Note that lis well defined when Ghas no loops. In F`abrega and Fiol [5] it was proved that, if a digraph G(different from a directed cycle) has semigirth l, then its line digraph L(G) has semigirth l+1. The diameter also has the same behaviour, that is, if the diameter of Gis D, then its line digraph L(G) has diameter D+ 1. We also recall two results from F`abrega and Fiol [5] on the connectivities and superconnectivities. Theorem 1 ([5]).Let G= (V, E)be a loopless digraph with minimum degree δ > 1, semigirth l, diameter Dand connectivities λand κ. (a)If D≤2l, then λ=δ. (b)If D≤2l−1, then κ=δ. Theorem 2 ([5]).Let G= (V, E)be a loopless digraph with minimum degree δ≥3, semigirth l, and diameter D. (a)If D≤2l, then Gis super-λ. (b)If D≤2l−2, then Gis super-κ. 1.3 Moore digraphs with respect to the diameter and the mean distance The Moore bound on the number of vertices for digraphs with diameter Dand maximum degree ∆ is N(∆, D) = ∆D+1−1 ∆−1. Notice that N∼O(∆D). The digraphs that attain the Moore bound N(∆, D) are called Moore digraphs. The only Moore digraphs are the directed cycles on D+1 vertices and the complete digraphs on ∆+1 vertices. For D > 1 and ∆ >1, there are no Moore digraphs. For more information, see the survey by Miller and ˇ Siraˇn [11]. The mean distance corresponding to a digraph attaining the Moore bound is given in the following result. Lemma 1. The mean distance ∂(∆, D)of a digraph attaining Moore digraphs with diameter Dand maximum degree ∆would be ∂(∆, D) = D∆D+2 −(1 + D)∆D+1 + ∆ ∆D+2 −∆D+1 −∆+1 . 5 210 2 1 K(2,1) K(2,2) 10 01 02 20 21 12 0 K(2,3) 101 010 102 020202 021 212 121 012 201 120 2 1 sK (2,1) sK (2,2) 10 01 02 20 21 12 0 sK (2,3) 101 010 210 102 020202 021 212 121 012 201 120 Figure 1: Some examples of Kautz and subKautz digraphs. Proof. We compute ∂(∆, D) taking into account that the maximum number of vertices at distance kis ∆k. ∂(∆, D) = 1 N(∆, D) D X k=0 k∆k=∆ N(∆, D) D X k=0 k∆k−1=∆ N(∆, D) D X k=0 ∆k!0 =∆ N(∆, D)∆D+1 −1 ∆−10 =D∆D+2 −(1 + D)∆D+1 + ∆ ∆D+2 −∆D+1 −∆+1 . We can define a digraph as optimal with respect to the diameter (the maximum delay in a message transmission), but also with respect to the mean distance (the average delay in a message transmission). So, we can say that a digraph is optimal when its mean distance tends to the exponent of the order of Nin terms of ∆, that is, when ∂∼O(log∆N). 2 Kautz-like digraphs Kautz K(d, `), subKautz sK(d, `), cyclic Kautz CK(d, `), and modified cyclic Kautz MCK(d, `) digraphs have vertices represented by words on an alphabet, and adjacencies between vertices correspond to shifts of the words. In these Kautz-like digraphs a path x→ycorresponds to a sequence beginning with x=x1x2. . . x`and finishing with y=y1y2. . . y`, where every subsequence of length `corresponds to a vertex of the corresponding digraph. 2.1 Kautz and subKautz digraphs Next, we recall the definitions of the Kautz K(d, `), and we define a new family of Kautzlike digraphs called subKautz digraphs sK(d, `). See examples of both in Figure 1. 6 CK (2,4) 0101 1012 0121 1212 2120 1202 2020 0201 2010 1010 2101 1210 2121 0212 2021 0202 1020 0102 MCK (2,4) 0101 1012 0121 1212 2120 1202 2020 0201 2010 1010 2101 1210 2121 0212 2021 0202 1020 0102 Figure 2: An example of a cyclic Kautz digraph and a modified cyclic Kautz digraph. AKautz digraph K(d, `) has vertices x1x2. . . x`, where xi∈Zd+1, with xi6=xi+1 for i= 1, . . . , ` −1, and adjacencies x1x2. . . x`→x2x3. . . x`y, y 6=x`. Given integers dand `, with d, ` ≥2, a subKautz digraph sK(d, `) has set of vertices V={x1x2. . . x`:xi6=xi+1, i = 1, . . . , ` −1, xi∈Zd+1}, and adjacencies x1x2. . . x`→x2. . . x`x`+1, x`+1 6=x1, x`.(1) Hence, the subKautz digraph sK(d, `) has d`+d`−1vertices, as the Kautz digraph K(d, `). Besides, the out-degree of a vertex x1x2. . . x`is dif x1=x`, and d−1 otherwise. In particular, the subKautz digraph sK(d, 2) is (d−1)-regular and can be obtained from the Kautz digraph K(d, 2) by removing all its arcs forming a digon. Note that the subKautz digraph sK(d, `) is a subdigraph of the Kautz digraph K(d, `). 2.2 Cyclic Kautz and modified cyclic Kautz digraphs Next, we recall the definitions of the cyclic Kautz digraphs CK(d, `) and the modified cyclic Kautz digraphs MCK(d, `). See an example of both in Figure 2. Acyclic Kautz digraph CK(d, `) has vertices x1x2. . . x`, where xi∈Zd+1, with xi6= xi+1 for i= 1, . . . , ` −1, and x`6=x1, and adjacencies x1x2. . . x`→x2x3. . . x`y, y 6=x1, x`. Note that the cyclic Kautz digraphs CK(d, `) are subdigraphs of the Kautz digraph K(d, `). It was proved in [3] that when d= 2 the cyclic Kautz digraphs CK(2, `) are not 7 connected (except for the case `= 4), and when `= 2 the cyclic Kautz digraphs CK(d, 2) coincide with the Kautz digraphs K(d, 2). Recall that the diameter of the Kautz digraphs is optimal, that is, for a fixed out-degree dand number of vertices (d+1)d`−1, the Kautz digraph K(d, `) has the smallest diameter (D=`) among all digraphs with (d+ 1)d`−1vertices and degree d(see, for example, Miller and ˇ Sir´aˇn [11]). Since the diameter of the cyclic Kautz digraphs CK(d, `) is greater than the diameter of the Kautz digraphs K(d, `), in [4] we constructed the modified cyclic Kautz digraphs MCK(d, `) by adding some arcs to CK(d, `), in order to obtain the same diameter as K(d, `), without increasing the maximum degree. In a cyclic Kautz digraph CK(d, `), a vertex labeled with a2. . . a`+1 is forbidden if a2=a`+1. For each label, we replace the first symbol a2by one of the possible symbols a0 2such that now a0 26=a3, a`+1 (so a0 2. . . a`+1 represents a vertex). Then, we add arcs from vertex a1. . . a`to vertex a0 2. . . a`+1, with a16=a`and a0 26=a3, a`+1. Note that CK(d, `) and MCK(d, `) have the same vertices, because we only add arcs to CK(d, `) to obtain MCK(d, `). Lemma 2. (a)The cyclic Kautz digraph CK(d, `)is the line digraph of the subKautz digraph sK(d, ` −1), that is, CK(d, `) = L(sK(d, ` −1)). (b)The modified cyclic Kautz digraph MCK(d, `)is the partial line digraph of the Kautz digraph K(d, ` −1), that is, MCK(d, `) = P L(sK(d, ` −1)). Proof. (a) From (1) we can write the arcs (x1x2. . . x`−1, x2. . . x`−1x`) of sK(d, ` −1) as x1x2. . . x`−1x`with xi6=xi+1 and x16=x`, which corresponds to the vertices of CK(d, `). Moreover, two arcs are adjacent in sK(d, ` −1) if x1x2. . . x`→x2. . . x`x`+1, where x16=x`, as required for the vertices of CK(d, `). (b) This was proved in [4]. In taking the partial line digraph, it suffices to consider only the arcs in K(d, ` −1) that are also in sK(d, ` −1). By using spectral techniques, the order nd,` of a cyclic Kautz digraph CK(d, `) was given in [2, 3]. Here we use a combinatorial proof of this result. Proposition 1. The order nd,` of a cyclic Kautz digraph CK(d, `)(that coincide with the size of the subKautz digraph sK(d, ` −1)) is nd,1=d+ 1 and nd,` =d`+ (−1)`dfor `≥2.(2) Proof. The number Nd,` of sequences x1x2. . . x`with xi6=xi+1 for i= 1, . . . , `−1 (vertices of K(d, `)) is d`+d`−1. Then, to compute nd,`, we must subtract from Nd,` the number n0 d,` of sequences x1x2. . . x`such that x1=x`. But this is the same as the number of sequences x2. . . x`with x26=x`, which is nd,`−1. Consequently, we get the recurrence nd,` =d`+d`−1−nd,`−1for `≥3.(3) Thus, (2) follows by applying recursively (3) and using that nd,2=d2+d. 8 In the following result we prove a way of finding a sK(d, `) a from Kautz digraphs K(d, `). We use the cyclic Kautz digraphs CK(d, `) in the proof. Lemma 3. The subKautz digraphs sK(d, `)can be obtained from Kautz digraphs K(d, `) by removing all the arcs of the closed walks of length `in the complete symmetric digraph K∗ d+1. Proof. From their definition, the subKautz digraphs sK(d, `) are obtained from K(d, `) by removing the arcs of the form x1x2. . . x`→x2. . . x`x1, which correspond to the vertices x1x2. . . x`x1of K(d, ` + 1), which in turn correspond to the closed walks of length `in the complete symmetric digraph K∗ d+1. The Kautz digraphs K(d, `) have d`+d`−1vertices and d`+1 +d`arcs. The number of vertices of sK(d, `) also is d`+d`−1, and we compute its number of arcs as follows. Since L(K(d, `)) = K(d, ` + 1) and L(sK(d, `)) = CK(d, ` + 1), to obtain the number of arcs of sK(d, `), we subtract to the number of arcs of K(d, `) the number of vertices of CK(d, `) (as in Proposition 1), that is, the size of sK(d, `) is d`+1 +d`−(d`+ (−1)`d) = d`+1 + (−1)`+1, which coincide with the order of CK(d, ` + 1). A simple property of symmetry shared by all the Kautz-like digraphs is the following. Lemma 4. Kautz digraphs K(d, `), subKautz digraphs sK(d, `), and cyclic Kautz digraphs CK(d, `)are isomorphic to their converses. Proof. Since the mapping Ψ(x1x2. . . x`) = x`. . . x2x1satisfies Ψ(Γ+(x1x2. . . x`))=Ψ(x2x3. . . x`y)=yx`. . . x3x2=Γ−(x`. . . x2x1)=Γ−(Ψ(x1x2. . . x`)), it is an isomorphism between every of such digraphs and its converse. 3 Routing, distances and cycles in CK(d, `) In this section, we consider d≥3 and `≥3 because, as said in the Introduction, when d= 2 the cyclic Kautz digraphs CK(2, `) are not connected (except for the case `= 4), and when `= 2, the cyclic Kautz digraphs CK(d, 2) coincide with the Kautz digraphs K(d, 2). We begin the study of the routing and distance in CK(d, `) with the case d, ` ≥4 and, afterwards, we deal with the case d= 3 or `= 3. 9 3.1 The case d, ` ≥4 For simplicity, and without loss of generality, we fix the length `of the sequences, for instance, assume that we are dealing with the cyclic Kautz digraph CK(d, 7) on the alphabet Zd+1 ={0,1, . . . , d}with d≥4. Let us consider two generic vertices: x=x1x2x3x4x5x6x7, y=y1y2y3y4y5y6y7, and the extended sequence of x, that is, ˜ x=x1x2x3x4x5x6x7x2x3x4x5x6x7, where xi∈Zd+1 \ {xi}. (Note that we also can interpret ˜ xas a set of sequences of length 2`−1.) Then, to find the distance dist(x,y), we compute the intersection ˜ xuy, which is the maximum final subsequence of xthat coincides with the initial subsequence of y. According to the length of such a subsequence, we distinguish three cases: (a)|˜ xuy|> ` −1 (⇒`−1≥ |xuy| ≥ 1): For instance, suppose that |xuy|= 4, so that we have the coincidence pattern: x1x2x3x4x5x6x7x2x3x4x5x6x7 [y1y2y3y4y5y6y7 where yi=xi+3 for i= 1,...,4, and (a1) y56=x2and y56=y4=x7, (a2) y66=x3, y5, (a3) y76=x4=y1and y76=y6. Then, the only shortest path from xto yis x=x1x2x3y1y2y3y4→x2x3y1y2y3y4y5→x3y1y2y3y4y5y6→y1y2y3y4y5y6y7=y. Hence, in this case, dist(x,y) = `− |xuy| ≤ `−1. To prove that the parameter lis at least `−1, we check that in this situation there is no x→ypath of length dist(x, y) + 1. Indeed, if y1=x4, then y16=x5as x46=x5. So, there is no path of length `, and l≥`−1. (b)|˜ xuy|=`−1: If y16=x7, we reason as in case (a) and we get dist(x,y) = `. Otherwise, if y1=x7, the sequence x2x3. . . x7y1does not correspond to any vertex. Then, we have to consider the ‘second largest’ intersection satisfying the next case: 1 ≤ |˜ xuy|< `−1. (Since `≥4, we prove later that this is always possible.) 16 Observe that, since CK(d, 3) is the line digraph of sK(d, 2), the respective mean distance satisfies the inequality δ < δ∗, in concordance with the results by Fiol, Yebra, and Alegre [7]. Also, note that the mean distances of sK(d, 2) and CK(d, 3), with d≥3, tend, respectively, to 2 and 3 for large degree d−1, that is, they are asymptotically optimal. References [1] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer- Verlag, London, 2007. [2] K. B¨ohmov´a, C. Dalf´o, C. Huemer, The diameter of cyclic Kautz digraphs, Electron. Notes Discrete Math. 49 (2015) 323–330. [3] K. B¨ohmov´a, C. Dalf´o, C. Huemer, On the diameter of cyclic Kautz digraphs, submitted (2016). [4] K. B¨ohmov´a, C. Dalf´o, C. Huemer, New cyclic Kautz digraphs with optimal diameter, submitted (2016). [5] J. F`abrega, M. A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (1989) 657–668. [6] M. A. Fiol, A. S. Llad´o, The partial line digraph technique in the design of large interconnection networks, IEEE Trans. Comput. 41 (1992) 848–857. [7] M. A. Fiol, J. L. A. Yebra, I. Alegre, Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Comput. C-33 (1984) 400–403. [8] D. Geller, F. Harary, Connectivity in digraphs, Lect. Notes Math. 186 (1970) 105–114. [9] W. H. Kautz, Bounds on directed (d, k) graphs, in Theory of Cellular Logic Networks and Machines, AFCRL-68-0668 Final Rep., 1968, 20–28. [10] J. H. van Lint, An Introduction to Coding Theory, 3rd edition, Springer-Verlag, New York, 1999. [11] M. Miller, J. ˇ Sir´aˇn, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2), #DS14v2, 2013. [12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.