Restricted arc-connectivity of generalized p-cycles

Restricted arc-connectivity of generalized p-cycles✩ C. Balbuenaa,∗, P. García-Vázquezb, A. Hansberga, L.P. Montejanoa aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain a r t i c l e i n f o Article history: Received 11 May 2011 Received in revised form 26 January 2012 Accepted 7 February 2012 Available online 26 February 2012 Keywords: Restricted arc-connectivity Generalized p-cycle Diameter Line digraph abstract For a strongly connected digraph Dthe restricted arc-connectivity λ′(D)is defined as the minimum cardinality of an arc-cut over all arc-cuts Ssatisfying that D−Shas a non-trivial strong component D1such that D−V(D1)contains an arc. In this paper we prove that a generalized p-cycle is λ′-optimal if diam(D)≤2ℓ+p−2, where ℓis the semigirth of Dand p≥3. Further we show that the k-iterated line digraph is λ′-optimal if diam(D)≤2ℓ+p−2+kfor p≥3. We improve these results for plarge enough and we also improve known results on super-λfor p-cycles with p≥3. 1. Introduction The digraphs (i.e. directed graphs) considered here have neither loops nor multiple arcs. The set of vertices and the set of arcs of a digraph Dis denoted by V(D)and A(D), respectively. For any arc uv∈A(D), the first vertex uis its tail and the second vertex vis its head. The head and tail of an arc are its end-vertices. A digraph is symmetric (resp. asymmetric), if the existence of an arc uv∈A(D)implies that vu∈A(D)(resp. vu∈ A(D)). The set of symmetric arcs of Dis denoted by Sym(D). If F⊂V(D), then D[F]is the subdigraph induced by F. The sets N+(u)= {v:uv∈A(D)}and N−(u)= {v:vu∈A(D)}are called the outneighborhood and in-neighborhood of the vertex u. The out-degree is d+(u)= |N+(u)|and the in-degree is d−(u)= |N−(u)|. The minimum out-degree of Dis δ+(D)=min{d+(u):u∈V(D)}and the minimum in-degree δ−(D)of Dis defined analogously. The minimum degree of Dis δ(D)=min{δ+(D), δ−(D)}. The distance from uto vis denoted by d(u, v) and is defined as the number of arcs of a shortest path from uto v. The parameter diam(D)=max{d(u, v) :u, v ∈V(D)}stands for the diameter of D. The distance from uto F⊂V(D)is d(u,F)=min{d(u,f):f∈F}. The distance from Fto v, d(F, v) is defined analogously. For any integer k≥1, let N+ k(F)= {u∈V(D):d(u,F)=k}and N− k(F)= {u∈V(D):d(F,u)=k}. Hence, when k=1 we have N+(x)=N+ 1(x), N−(x)=N− 1(x),N+(F)=N+ 1(F)and N−(F)=N− 1(F). For any pair of vertices u, v ∈V(D), a path uu1· · · ur−1vfrom uto vwith all its vertices different is called an u→v path. An u→upath is a cycle. The length of a shortest cycle is the girth g of D. A digraph Dis said to be strongly connected if for any pair of vertices u, v ∈V(D)there exists an u→vpath. Clearly, a digraph Dis strongly connected if and only if diam(D) < ∞. For a pair U,Fof vertex sets of a digraph D, we define [U,F]={uf ∈A(D):u∈U,f∈F}. If [U,F]=∅we say that there is no UF-arc in D. If F=V(D)\U, we write ω+(U)or ω−(F)instead of [U,F]. When U= {u}we abbreviate ω+({u})and ω−({u})to ω+(u)and ω−(u), respectively. Clearly d+(u)= |ω+(u)|and d−(u)= |ω−(u)|for all u∈V(D). ✩This research was supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2011-28800-C02-02; and under the Catalonian Government project 1298 SGR2009; the third author was also partially supported by a Juan de la Cierva Postdoctoral Fellowship. ∗Corresponding author. Tel.: +34 3 401 69 17; fax: +34 3 401 65 04. E-mail addresses: [email protected] (C. Balbuena), [email protected] (P. García-Vázquez), [email protected] (A. Hansberg), [email protected] (L.P. Montejano). 0166-218X/$ – 1326 Let Dbe a strongly connected digraph. A subset S⊆A(D)of arcs is an arc-cut if D−Sis not strongly connected. Note that each minimum arc-cut has the form ω+(F), where F⊂V(D). Thus, the arc-connectivity λof a digraph Dcan be defined as λ(D)=min{|ω+(F)| : F⊂V(D), F= ∅,F= V(D)}. It is well-known that for any digraph D, λ(D)≤δ(D)[11]. Hence, Dis said to be maximally arc-connected if λ(D)=δ(D). Following Hamidoune [14,15], a subset Fof vertices of a strongly connected digraph Dwith arc-connectivity λis a positive α-fragment if |ω+(F)| = λand similarly, Fis a negative α-fragment if |ω−(F)| = λ. Note that Fis a positive α-fragment if and only if F=V(D)\Fis a negative α-fragment. Given an arc cut S=ω+(F)= [F,F], we will write X⊆Fand X⊆Ffor the sets of vertices in Fand Fincident with the arcs of S. That is, every arc of Shas its out-vertex in Xand its in-vertex in X. The arc-connectivity is an important measure for the fault tolerance of a network. However, one might be interested in more refined indices of reliability. Even two graphs or digraphs with the same arc-connectivity λmay be considered to have different reliabilities, since the number or type of minimum arc-cuts is different or simply because the existence of some additional structural properties is required. From here arises the notion of restricted arc-connectivity which extends the notion of restricted edge-connectivity of graphs. Volkmann [19] extended the concept of restricted edge-connectivity to digraphs as follows. Definition 1.1 ([19]).Let Dbe a strongly connected digraph. An arc set Sof Dis a restricted arc-cut of Dif D−Shas a non-trivial strong component D1such that D−V(D1)contains an arc. The restricted arc-connectivity λ′(D)is defined as the minimum cardinality over all restricted arc-cuts S. A strongly connected digraph Dis called λ′-connected if λ′(D)exists. A restricted arc-cut Sis called a λ′-cut if |S| = λ′(D). Note that if λ<δ, then λ′=λ. Moreover, if λ=δand there is a non-trivial arc-cut of cardinality δ, then λ=λ′=δ. Otherwise, if λ=δand every arc-cut of cardinality δis trivial, then the digraph is called super arc-connected or super-λin which case λ′> δ. For more information on super arc-connectivity see for instance [5,7,9,8,16,14]. Volkmann proved that every strong digraph Dof order n≥4 and girth g=2,3 not belonging to some families of digraphs is λ′-connected and satisfies λ(D)≤λ′(D)≤ξ(D), where ξ(D)is defined as follows. If Cg=u1u2· · · ugu1is a shortest cycle of D, then ξ(Cg)= min{g i=1d+(ui)−g,g i=1d−(ui)−g}, and ξ(D)=min{ξ(Cg):Cgis a shortest cycle of D}. Later, in 2008, Wang and Lin [20] introduced the notion of arc-degree which turns to be a better bound for the parameter λ′. The arc-degree is defined as follows. For any arc uv∈A(D), the arc-degree of uvis defined as ξ′(uv) =min{|ω+({u, v})|,|ω−({u, v})|,|ω+(u)∪ ω−(v)|,|ω−(u)∪ω+(v)|} and the minimum arc-degree of Dis ξ′(D)=min{ξ′(uv) :uv∈A(D)}. We can compute the arc-degree of an arc uv∈A(D)in terms of the degrees of the vertices uand v. If uv∈ Sym(D), then ξ′(uv) =min{d+(u)+d+(v) −1,d−(u)+d−(v) −1,d+(u)+d−(v) −1,d−(u)+d+(v)}. If uv∈Sym(D), then ξ′(uv) =min{d+(u)+d+(v) −2,d−(u)+d−(v) −2,d+(u)+d−(v) −1,d−(u)+d+(v) −1}. It is clear from this definition that for many digraphs ξ′(D)≤ξ(D), for instance for digraphs with δ≥3. Given an arc uv∈A(D)we set Ωuv= {ω+({u, v}), ω−({u, v}), ω+(u)∪ω−(v), ω−(u)∪ω+(v)}. Note that for every arc uv∈A(D)of a strongly connected digraph D, the elements of Ωuvare arc-cuts of Dbut they are not necessarily restricted arc-cuts. As an example, consider the cycle of length k≥3. In the aforementioned paper [20], Wang and Lin proved the following result. Theorem 1.1 ([20]).Let D be a strongly connected digraph with δ+(D)≥3or δ−(D)≥3. Then every element of Ωuvis a restricted arc-cut for any uv∈A(D)and thus D is λ′-connected. Further, λ′(D)≤ξ′(D). Definition 1.2. A digraph Dis λ′-optimal if λ′(D)=ξ′(D). Some sufficient conditions for some families of digraphs to attain λ′-optimality can be found in [3,6,20]. The purpose of this paper is to state sufficient conditions to assure λ′-optimality in a special kind of digraphs: generalized cycles. A generalized p-cycle is a digraph Din which its set of vertices can be partitioned into p≥2 parts, V= α∈Zp Vα, in such a way that the vertices in the partite set Vαare only adjacent to vertices in Vα+1, where the sum is in Zp. Observe that bipartite digraphs are generalized p-cycles with p=2. Gómez et al. showed in [12] that a digraph is a generalized p-cycle if and only if for any pair of vertices u, v, the lengths of all paths from uto vare congruent modulo p. In the same paper they prove that a digraph Dis a generalized p-cycle if and only if, its line digraph is a generalized p-cycle as well. We recall here that in the line digraph L(D)of a digraph D, each vertex represents an arc of D. Thus, V(L(D)) = {uv:uv∈A(D)}; moreover, a vertex uvis adjacent to a vertex xz if and only if v=x, that is, when the arc uvis incident to the arc xz in D. From the definition it follows that δ(L(D)) =δ(D)=δ. For any k≥1 the k-iterated line digraph,Lk(D), is defined recursively by Lk(D)=L(Lk−1(D)). It was shown in [1] that the diameter of any strongly connected digraph other than a directed cycle satisfies diam(Lk(D)) =diam(D)+k.(1) For more information on line digraphs see, for instance, [10,18]. 1327 A parameter related to the number of shortest paths was introduced by Fàbrega and Fiol in [7], which has received the name of semigirth, see The Handbook of Graph Theory [13]. Given a digraph D, the semigirth ℓof Dis defined as the greatest integer such that, for any x,y∈V, (a) if d(x,y)≤ℓ, the shortest x→ypath is unique; (b) if d(x,y)≤ℓ−1, there is no x→ypath of length d(x,y)+1. Observe that the semigirth is well defined because the digraphs are assumed to be simple. Also note that if Gis a graph with girth g, then the semigirth of the symmetric digraph −→ Gis ℓ(−→ G)= ⌊(g(G)−1)/2⌋. Also note that if a digraph Dis a generalized p-cycle, the condition (b) is unnecessary. To show that there always exists a digraph with a given semigirth ℓ, it was shown [7] that for any digraph Dwith minimum degree δ≥2 the semigirth ℓalso satisfies an equality like (1). Namely, ℓ(Lk(D)) =ℓ(D)+k.(2) Using the semigirth in [17], the authors show that any p-cycle Dwith minimum degree δ≥2 and diameter diam(D)≤ 2ℓ+p−1 has λ=δ(this result is shown for p=2 in [7]). Later, in [4], the same authors prove that a generalized p-cycle with p≥3 is super-λif diam(D)≤2ℓ+p−2. Moreover in [2,8] it was proved that any bipartite digraph with minimum degree δ≥3 and diam(D)≤2ℓis super-λ. In this paper, we prove that a generalized p-cycle is λ′-optimal if the diameter is at most diam(D)≤2ℓ+p−2 for p≥3 and diam(D)≤2ℓ2−1 for p=2, where ℓ2is a parameter which coincides with the semigirth ℓwhen p≥3. Furthermore, we show that the k-iterated line digraph Lk(D)of a digraph is λ′-optimal if the diameter of Dis at most diam(D)≤2ℓ+p−2+k for p≥3 and diam(D)≤2ℓ2−1+kfor p=2. Moreover, we prove that a generalized p-cycle with p≥3 is super-λif diam(D)≤2ℓ+p−1, which improves the sufficient condition given in [4]. Finally, we also improve these results for p large enough. 2. Main results In order to study the restricted arc-connectivity of generalized p-cycles, we slightly modify the semigirth by defining a new parameter ℓ2which coincides with ℓwhen p≥3. In particular ℓ2will be very useful when dealing with bipartite digraphs. Definition 2.1. For a given digraph D, let ℓ2=ℓ2(D), 1≤ℓ2≤diam(D), be the greatest integer such that, for any x,y∈V, (a) if d(x,y)≤ℓ2, the shortest x→ypath is unique; (b) if d(x,y)≤ℓ2−t, there is no x→ypath of length d(x,y)+tfor 1 ≤t≤2. Observe that ℓ2is well defined in oriented digraphs, that is in digraphs with girth at least 3. Hence, from now all the digraphs we dealt with are assumed to have girth at least 3. The parameter ℓ2satisfies, as the semigirth, an equality like (2). Remark 2.1. Let Dbe a strongly connected digraph with girth at least three other than a cycle. Then ℓ2(Lk(D)) =ℓ2(D)+k. Proof. As L(Lk−1(D)) =Lk(D), it is enough to prove the case k=1. Take u=(u1u2), v =(v1v2)∈V(L(D)) such that dL(D)(u, v) ≤ℓ2(D)+1. First, assume u=vso that dL(D)(u, v) =0. Since Dand L(D)have the same girth it follows that the girth of L(D)is at least three yielding there is no u→upath of length at most two. Thus assume that u= v. Then dD(u2, v1)=dL(D)(u, v) −1≤ℓ2(D)and hence the shortest u2→v1path in Dis unique implying that the shortest u→v path in L(D)is unique. If dL(D)(u, v) ≤ℓ2(D)−1, then dD(u2, v1)≤ℓ2(D)−2 meaning that there is no u2→v1path of length dD(u2, v1)+2 in Dby Definition 2.1, and so there is no u→vpath of length dL(D)(u, v) +2 in L(D). Thus we have proved that ℓ2(L(D)) ≥ℓ2(D)+1. We will show now that ℓ2(L(D)) =ℓ2(D)+1. If ℓ2(D)=diam(D), it follows by (1) that ℓ2(L(D)) =ℓ2(D)+1. Suppose now that ℓ2(D) < diam(D). In view of the definition of ℓ2(D)we distinguish two cases. Case 1. There are vertices x,y∈V(D)such that dD(x,y)=ℓ2(D)+1 and there are at least two shortest x→y paths in D. Since Dis strongly connected there have to be vertices x′,y′∈V(D)with x′x,yy′∈A(D). Now, considering u=(x′x)and v=(yy′)in V(L(D)), it follows that there are two shortest u→vpaths of length ℓ2(D)+2. This implies that ℓ2(L(D)) ≤ℓ2(D)+1. Case 2. There are vertices x,y∈V(D)such that dD(x,y)=ℓ2(D)−1 and there is an x→ypath of length ℓ2(D)+1. Since Dis strongly connected, there have to be vertices x′,y′∈V(D)with x′x,yy′∈A(D). Now, considering u=(x′x)and v=(yy′)in V(L(D)), it follows that dL(D)(u, v) =ℓ2(D)and that there is an u→vpath of length ℓ2(D)+2. This implies that ℓ2(L(D)) ≤ℓ2(D)+1. Hence ℓ2(L(D)) =ℓ2(D)+1 and therefore ℓ2(Lk(D)) =ℓ2(D)+k. Recently, we proved a similar result as Theorem 1.1, changing the hypothesis δ+(D)≥3 or δ−(D)≥3 for δ(D)≥2. Lemma 2.1 ([3]).Let D be a strongly connected digraph of order at least 4and minimum degree δ≥2. Then D is λ′-connected and λ′(D)≤ξ′(D). 1328 The following lemma was also proved in [3]. Lemma 2.2 ([3]).Let D be a λ′-connected digraph such that λ′(D)<ξ′(D)and let S be a λ′-cut. Then the set V can be partitioned into two subsets, F,F such that S =ω+(F)=ω−(F)and both induced subdigraphs D[F]and D[F]of D contain an arc. Throughout this paper, if Dis a λ′-connected and non λ′-optimal digraph, then F,F⊂V(D)can be considered by Lemma 2.2, so that ω+(F)=ω−(F)= [F,F]=[X,X]is a λ′-cut, where Xand Xare the sets of vertices in Fand Fwhich are incident with arcs from ω+(F). Let us define µ(F)=max{d(u,X):u∈F}and µ(F)=max{d(X,u):u∈F}. Also, we will use the following notation: F≥ m= {u∈F:d(u,X)≥m},F≥ m= {v∈F:d(X, v) ≥m},Fm= {u∈F:d(u,X)=m}and Fm= {v∈F:d(X, v) =m}. Some properties concerning ℓ2on non λ′-optimal digraphs are provided in the following results. First, we prove the following lemma which shows that the parameter ℓ2is a suitable index to measure how far away a vertex of a non λ′-optimal generalized p-cycle can be from a λ′-cut. Lemma 2.3. Let D be a λ′-connected generalized p-cycle with δ≥2such that λ′(D) < ξ′(D). Let ω+(F)be a λ′-cut. Then µ(F)≥max{1, ℓ2−1}and µ(F)≥max{1, ℓ2−1}. Proof. Let ω+(F)= [F,F]=[X,X]be a λ′-cut. First assume that µ=µ(F)=0. This implies that F=X. By Lemma 2.2, we can consider an arc uvin D[F]. Note that, since Dis a generalized p-cycle, N+(u)∩N+(v) = ∅. Then λ′(D)= |[X,X]| ≥ |X| ≥ |[{u, v},X]| + |[(N+(u)−v) ∩X,X]| + |[(N+(v) −u)∩X,X]| ≥ |N+(u)−v|+|N+(v) −u| = |ω+({u, v})| ≥ ξ′(uv) ≥ξ′(D), which is a contradiction. Hence, µ≥1. Assume by contradiction that 1 ≤µ≤ℓ2−2, which means that ℓ2≥3 and so the girth is at least three. Let us study the following cases. Case 1: There exists an arc uvin D[Fµ], see Fig. 1. Since Dis a generalized p-cycle, the sets N+(u)∩Fµ−1,Au=(N+(u)−v) ∩Fµ,N+(v) ∩Fµ−1and Av=N+(v) ∩Fµ are pairwise disjoint. Define A1=N+ µ(u)∩X,A2=N+ µ(Au)∩X,A3=N+ µ(v) ∩Xand A4=N+ µ(Av)∩Xand note that d(w, x)≥µfor any w∈Fµand any x∈X. We will now show that the sets A1,A2,A3and A4are pairwise disjoint. If there is a vertex a∈A1∩A2, then d(u,a)=µand there is also an u→apath of length µ+1, which is not possible in a generalized p-cycle. Analogously it can be shown that A1∩A3= ∅,A3∩A4= ∅ and A2∩A4= ∅. Now suppose that there is a vertex a∈A1∩A4. Then evidently d(u,a)=µand there is also an u→apath of length µ+2 (which can only occur if p=2). This contradicts the definition of ℓ2. Similarly, if there is a vertex a∈A2∩A3, then d(u,a)=µ+1 and there are two distinct u→apaths of length µ+1, contradicting again the definition of ℓ2. On the other side, by similar arguments one can show |A1|≥|N+(u)∩Fµ−1|,|A2|≥|(N+(u)−v) ∩Fµ|,|A3|≥|N+(v) ∩Fµ−1|and |A4|≥|N+(v) ∩Fµ|. Hence, λ′(D)= |[X,X]| ≥ |X|≥|A1|+|A2|+|A3|+|A4| ≥ |N+(u)∩Fµ−1| + |(N+(u)−v) ∩Fµ| + |N+(v) ∩Fµ−1| + |N+(v) ∩Fµ| = |ω+({u, v})| ≥ ξ′(uv) ≥ξ′(D), a contradiction to the hypothesis λ′(D)<ξ′(D). Case 2: There is no arc uvin D[Fµ], see Fig. 2. Let u∈Fµand take any v∈N+(u)∩Fµ−1. Define A1=N+ µ−1(N+(u)−v) ∩X,A2=N+ µ−1(v) ∩X,A3= N+ µ−1(N+(v) ∩Fµ−1)∩Xand A4=N+ µ(N+(v) ∩Fµ)∩X. By similar arguments as in Case 1, one can show that A1,A2,A3 and A4are pairwise disjoint. Thus, if a∈A1∩A4then we find two distinct u→apaths, one of length µand another through vertex vof length µ+2 which contradicts the definition of ℓ2. Also as above, it is straightforward to prove that |A1|≥|N+(u)−v|,|A2|≥|N+(v) ∩Fµ−2|,|A3|≥|N+(v) ∩Fµ−1|, and |A4|≥|N+(v) ∩Fµ|. Thus, λ′(D)= |[X,X]| ≥ |X|≥|A1|+|A2|+|A3|+|A4| ≥ |N+(u)−v| + |N+(v) ∩Fµ−2| + |N+(v) ∩Fµ−1| + |N+(v) ∩Fµ| = |ω+({u, v})| ≥ ξ′(uv) ≥ξ′(D), a contradiction to the fact that λ′(D)<ξ′(D). Altogether it follows that µ≥ℓ2−1. The proof of µ≥ℓ2−1 is analogous. So the result holds.  Lemma 2.4. Let D be a λ′-connected generalized p-cycle with ℓ2≥2and minimum degree δ≥2such that λ′(D) < ξ′(D). Let ω+(F)be a λ′-cut. If there is a vertex u ∈Fmfor 1≤m≤ℓ2such that N+(u)⊆Fm−1, then N+(v) ∩F≥ m= ∅ for all v∈N+(u). 1329 Fig. 1. Case 1: There exists an arc uvin D[Fµ]. Fig. 2. Case 2: There is no arc uvin D[Fµ]. Proof. Let ω+(F)= [F,F] = [X,X]. Suppose that N+(v) ∩F≥ m= ∅ for some v∈N+(u). First assume that m≥2 and consider the sets A1=N+ m−1(N+(u)−v)∩X,A2=N+ m−1(v)∩Xand A3=N+ m−1(N+(v)∩Fm−1)∩X. Similarly as in the proof of Lemma 2.3, one can show that A1,A2and A3are pairwise disjoint and that |A1| ≥ |N+(u)−v|,|A2| ≥ |N+(v) ∩Fm−2| and |A3|≥|N+(v) ∩Fm−1|. Hence, λ′(D)= |[X,X]| ≥ |X|≥|A1|+|A2| + |A3|≥|ω+({u, v})| ≥ ξ′(D), a contradiction to the hypothesis. If m=1, consider the sets A1=N+(N+(u)−v) ∩X,A2=N+(v) ∩Xand A3=N+(N+(v) ∩X)∩Xand proceed as above obtaining a similar contradiction.  Lemma 2.5. Let D be a λ′-connected generalized p-cycle with minimum degree δ≥2such that λ′(D) < ξ′(D). Let ω+(F)be a λ′-cut such that µ(F)=ℓ2−1. Then D[Fℓ2−1]contains an arc. Proof. Let ω+(F)= [F,F]=[X,X]. Note that by Lemma 2.3, 1 ≤µ(F)=ℓ2−1, i.e., ℓ2≥2. Assume by contradiction that N+(u)∩Fℓ2−1= ∅ for all u∈Fℓ2−1. Take any u∈Fℓ2−1and let v∈N+(u)⊆Fℓ2−2. By Lemma 2.4, there is a vertex w∈N+(v) ∩Fℓ2−1. Thus N+(w) ∩Fℓ2−1= ∅. First suppose that ℓ2≥3 and consider the sets A1=N+ ℓ2−2(v) ∩X,A2=N+ ℓ2−2(N+(v) ∩Fℓ2−2)∩X,A3=N+ ℓ2−1(N+(v) −w) ∩Fℓ2−1∩Xand A4=N+ ℓ2−1(w) ∩X. Similarly as in Lemma 2.3, it is straightforward to show that the sets A1,A2,A3and A4are pairwise disjoint and that |A1|≥|N+(v) ∩Fℓ2−3|,|A2|≥|N+(v) ∩Fℓ2−2|,|A3|≥|(N+(v) −w) ∩Fℓ2−1|and |A4|≥|N+(w) ∩Fℓ2−2|. Therefore, |ω+(F)| = |[X,X]| ≥ |X|≥|A1| + |A2| + |A3| + |A4| ≥ |N+(v) ∩Fℓ2−3| + |N+(v) ∩Fℓ2−2| + |(N+(v) −w) ∩Fℓ2−1| + |N+(w) ∩Fℓ2−2| =ω+({v, w})≥ξ′(D), a contradiction. If ℓ2=2, consider the sets A1=N+(v) ∩X,A2=N+(N+(v) ∩X)∩X,A3=N+ 2((N+(v) −w) ∩F1)∩X and A4=N+ 2(w) ∩Xand proceed as above obtaining a similar contradiction. Altogether it follows that there has to be an arc in D[Fℓ2−1]. 1330 The following lemma is an improvement of Lemma 2.3 for generalized p-cycles with p≥3. Lemma 2.6. Let D be a λ′-connected generalized p-cycle with p ≥3and minimum degree δ≥2such that λ′(D)<ξ′(D). Let ω+(F)be a λ′-cut. Then µ(F), µ(F)≥ℓ. Proof. Let ω+(F)= [F,F]=[X,X]. From Lemma 2.3, it follows that µ=µ(F)≥max{1, ℓ −1}. We reason by contradiction assuming that µ=ℓ−1≥1 so that ℓ≥2. By Lemma 2.5, there exists an arc uvin D[Fℓ−1]. Define A1= N+ ℓ−1({u, v})∩X,A2=N+ ℓ−1(N+(u)−v) ∩Xand A3=N+ ℓ−1(N+(v)) ∩X. Since p≥3 and by the definition of the semigirth ℓ, A1,A2,A3are pairwise vertex-disjoint. By the same reason, |A1|≥|(N+(u)∪N+(v)) ∩Fℓ−2|,|A2|≥|(N+(u)−v) ∩Fℓ−1|, and |A3|≥|N+(v) ∩Fℓ−1|. Therefore, |ω+(F)| ≥ |X|≥|A1| + |A2| + |A3| ≥ |(N+(u)∪N+(v)) ∩Fℓ−2| + |(N+(u)−v) ∩Fℓ−1| + |N+(v) ∩Fℓ−1| =ω+({u, v})≥ξ′(D), a contradiction. Thus µ≥ℓ. By considering the converse digraph, µ(F)≥ℓcan be shown.  Lemma 2.7. Let D be a λ′-connected generalized p-cycle with minimum degree δ≥2such that λ′(D) < ξ′(D). Let ω+(F)= [F,F]be a λ′-cut. Then D[F≥ ℓ2−1]and D[F≥ ℓ2−1]contain a cycle. Proof. Let ω+(F)= [F,F] = [X,X]. From Lemma 2.3, it follows that µ=µ(F)≥max{1, ℓ2−1}. Two cases need to be distinguished: Case 1. Assume that µ=ℓ2−1. Hence µ=ℓ2−1≥1. Then, from Lemma 2.5, it follows that D[Fℓ2−1]contains an arc uv. If N+(v) ∩Fℓ2−1= ∅, then λ′(D)= |ω+(F)|≥|X|≥|(N+ ℓ2−1({u, v})∪N+ ℓ2−1((N+(u)−v) ∩Fℓ2−1)) ∩X|≥|ω+({u, v})| ≥ ξ′(D), which is a contradiction. Thus N+(v) ∩Fℓ2−1= ∅. Therefore, we have proved that from the head of each arc of D[Fℓ2−1] follows another arc in D[Fℓ2−1], implying the existence of a cycle in D[Fℓ2−1]. Similarly, if µ=ℓ2−1, one can show that there exists a cycle in D[Fℓ2−1]. Case 2. Assume that µ≥ℓ2. If there is a cycle contained in D[F≥ ℓ2], then we are done. Thus, we suppose to the contrary that there is no cycle contained in D[F≥ ℓ2]. Let u∈F≥ ℓ2. Then there has to be a path from uto a vertex u′∈Fℓ2such that N+(u′)⊆Fℓ2−1. By Lemma 2.4, N+(v) ∩F≥ ℓ2= ∅ for every v∈N+(u′). Considering a vertex w∈N+(v) ∩F≥ ℓ2and reasoning for was above for uand so successively, we can guarantee the existence of a cycle in D[F≥ ℓ2−1]. Similarly, if µ≥ℓ2, one can show that there exists a cycle in D[Fℓ2−1]. In the next lemma we give a condition to guarantee how large is the diameter in a generalized p-cycle in terms of the deepness of the fragments of a given arc-cut. Lemma 2.8. Let D be a strongly connected generalized p-cycle with vertex partition ∪a∈ZpVαand let ω+(F)be an arc-cut. Let m,t≥0be two integers and suppose that for every α∈Zp,F≥ m∩Vα= ∅ and F≥ t= ∅, or F≥ t∩Vα= ∅ and F≥ m= ∅. Then diam(D)≥p+m+t. Proof. Let ω+(F)= [F,F] = [X,X]. Assume that F≥ m∩Vα= ∅ for every α∈Zpand F≥ t= ∅; the proof for the other case is analogue. Consider the integer r∈Zp, such that diam(D)≡r−1(mod p). As F≥ t= ∅, there is an α∈Zpsuch that F≥ t∩Vα= ∅. Take any vertex v∈F≥ t∩Vα. By hypothesis, F≥ m∩Vα+r= ∅, so take any vertex u∈F≥ m∩Vα+r. Then d(u, v) ≡r(mod p)yielding d(u, v) < diam(D), which implies that there is an integer h≥1 such that d(u, v) ≤diam(D)+1−hp ≤diam(D)+1−p. Since m+1+t≤d(u, v), it follows that diam(D)≥p+m+t. Now, we are able to prove the main result of this paper. Theorem 2.1. Let D be a generalized p-cycle with minimum degree δ≥2. Then D is λ′-optimal if (a) diam(D)≤2ℓ2−1for p =2; (b) diam(D)≤2ℓ+p−2for p ≥3. Proof. Note that the conditions δ≥2 and p≥2 imply that Dhas order at least 4. From Lemma 2.1 it follows that Dis λ′-connected and λ′(D)≤ξ′(D). Suppose that Dis not λ′-optimal and let ω+(F)= [F,F] = [X,X]be a λ′-cut. (See Lemma 2.2.) (a) Let p=2 and suppose that diam(D)≤2ℓ2−1. By Lemma 2.3,µ, µ ≥max{1, ℓ2−1}so that Fℓ2−1= ∅. By Lemma 2.7, there exists a cycle in D[F≥ ℓ2−1]which has to contain vertices from each part Vα, α ∈Z2. Therefore, F≥ ℓ2−1∩Vα= ∅ for every α∈Z2. Hence Lemma 2.8 implies that diam(D)≥2+(ℓ2−1)+(ℓ2−1)=2ℓ2, which is a contradiction to the hypothesis. 1331 (b) Let p≥3 and suppose that diam(D)≤2ℓ+p−2. By Lemma 2.6,µ, µ ≥ℓso that Fℓ= ∅. By Lemma 2.7, there exists a cycle in D[F≥ ℓ−1]which has to contain vertices from each part Vα, α ∈Zp, as Dis a generalized p-cycle. Therefore, F≥ ℓ−1∩Vα= ∅ for every α∈Zp. Hence Lemma 2.8 implies that diam(D)≥p+(ℓ −1)+ℓ=p+2ℓ−1, which is a contradiction to the hypothesis.  In the following lemma we show that the larger the quotient p |X|of a non λ′-optimal generalized p-cycle Dwith λ′-cut ω+(F)= [F,F]=[X,X]is, the deeper the fragments of Dhave to be. Lemma 2.9. Let D be a λ′-connected generalized p-cycle with minimum degree δ≥2such that λ′(D)<ξ′(D)and p ≥3. Let ω+(F)= [F,F]=[X,X]be a λ′-cut. Then µ(F)≥ℓ−2+ ⌈ p |X|⌉and µ(F)≥ℓ−2+ ⌈ p |X|⌉. Proof. By Lemma 2.6,µ≥ℓ, and by Lemma 2.7, there exists a cycle in D[F≥ ℓ−1]which has to contain vertices from each class Vα, α ∈Zp. Note that the set of vertices of D[F≥ ℓ−1]is µ j=ℓ−1Fj. Then there exists an index j∈ {ℓ−1, ℓ, . . . , µ}such that Fj has vertices of at least p µ−ℓ+2different classes, because otherwise D[F≥ ℓ−1]will not contain vertices of each class, which is a contradiction. As Dis a generalized p-cycle, Xhas to contain vertices from at least the same number of classes that appear in Fj. Thus, |X| ≥ p µ−ℓ+2, implying that µ≥ℓ−2+ ⌈ p |X|⌉. The proof of µ(F)≥ℓ−2+ ⌈ p |X|⌉follows analogously.  The following theorem gives an improvement of Theorem 2.1 for p-cycles with p> ξ′≥3. Theorem 2.2. Let D be a generalized p-cycle with minimum degree δ≥2and p ≥3. If diam(D)≤2ℓ+p−4+ ⌈ p ξ′(D)⌉, then D is λ′-optimal. Proof. From Lemma 2.1 it follows that Dis λ′-connected and λ′(D)≤ξ′(D). Suppose that Dis not λ′-optimal and let ω+(F)= [F,F]=[X,X]be a λ′-cut and m= ⌈ p ξ′(D)⌉−1. By Lemma 2.9,µ(F)≥ℓ−2+⌈ p |X|⌉ ≥ ℓ−2+⌈ p ξ′(D)⌉ = ℓ−1+m. Moreover, by Lemma 2.7, there exists a cycle in D[F≥ ℓ−1]and thus F≥ ℓ−1∩Vα= ∅ for every α∈Zp. Since Fℓ−1+m= ∅ as µ(F)≥ℓ−1+m,Lemma 2.8 implies that diam(D)≥p+(ℓ −1)+(ℓ −1+m)=p+2ℓ−2+m=p+2ℓ−3+ ⌈ p ξ′(D)⌉, which is a contradiction to the hypothesis.  Next, we give sufficient conditions for the k-iterated line digraph to be λ′-optimal. Corollary 2.1. Let D be a generalized p-cycle with minimum degree δ≥2. Then, Lk(D)is λ′-optimal if: (a) diam(D)≤2ℓ2−1+k for p =2, (b) diam(D)≤2ℓ+p−2+k for p ≥3, or (c) diam(D)≤2ℓ+p−4+ ⌈ p ξ′(D)⌉ + k and p ≥3. Proof. From Lemma 2.1 it follows that Dis λ′-connected and λ′(D)≤ξ′(D). By Remark 2.1,Lk(D)has parameter ℓ2+k. From (1) and the hypothesis diam(D)≤2ℓ2−1+kit follows that diam(Lk(D)) =diam(D)+k≤2ℓ2−1+2k. Hence (a) follows directly from Theorem 2.1(a). The proof of (b) follows analogously. Similarly, from (1) and Theorem 2.2, (c) follows.  Theorem 2.3. Let D be a generalized p-cycle with minimum degree δ≥2and p ≥3. If diam(D)≤2ℓ+p−1, then D is super-λ and λ′(D)>δ. Proof. From Lemma 2.1 it follows that Dis λ′-connected and λ′(D)≤ξ′(D). Suppose that Dis not super-λ, i.e., λ′(D)≤δ. Then Dis not λ′-optimal and, by Lemma 2.2, there is a λ′-cut ω+(F)= [F,F]=[X,X]. By Lemma 2.6 we have µ=µ(F)≥ℓ and µ=µ(F)≥ℓ. Suppose that there exists a cycle in D[F≥ ℓ]. Then F≥ ℓ∩Vα= ∅ for every α∈Zp. Hence, as Fℓ= ∅, Lemma 2.8 implies that diam(D)≥ℓ+ℓ+p=2ℓ+p, which is a contradiction to the hypothesis. Therefore there is no cycle in D[F≥ ℓ]and analogously there is no cycle in D[F≥ ℓ]. Thus we may assume that there exists a vertex u∈Fℓsuch that N+(u)∩F≥ ℓ= ∅ and there exists a vertex u∈Fℓsuch that N+(u)∩F≥ ℓ= ∅. Let v∈N+(u)and consider the sets A1=(N+ ℓ−1(N+(u)−v)) ∩Xand A2=(N+ ℓ−1(N+(v) ∩Fℓ−1)∪N+ ℓ(N+(v) ∩Fℓ)∪ Nℓ−1(v)) ∩X. By the definition of ℓand because p≥3,|A1| ≥ |N+(u)−v| ≥ δ−1 and A1∩A2= ∅. If |A2| ≥ 2 then λ′(D)≥ |X|≥|A1| + |A2| ≥ δ+1, a contradiction. Thus |A2| = 1, that is, A2=N+ ℓ−1(v) ∩Xyielding N+(v) ∩F≥ ℓ+1= ∅, because δ≥2. This means that µ≥ℓ+1 and reasoning analogously µ≥ℓ+1. 1332 Let A3=(N+ j(N+(v) ∩F≥ ℓ+1)) ∩Xwith ℓ+1≤j≤µ. Note that A3cannot be disjoint with A1∪A2because |X| = δ. Therefore there exists x∈Xand two distinct paths from uto x, namely the shortest one of length ℓand another through vertex vwhose length is greater than ℓand congruent with ℓmodulo pbecause Dis a p-cycle. This means that µ≥ℓ+p−2. Then taking a vertex z∈Fµand another z∈Fℓ+1it follows that diam(D)≥d(z,z)≥d(z,X)+1+d(X,z)≥µ+1+(ℓ+1)≥ (ℓ +p−2)+ℓ+2=2ℓ+pwhich is a contradiction to the hypothesis. Thus Dis super-λand λ′(D)>δ. Acknowledgments We want to deeply thank the anonymous referees who helped us to improve this paper. References [1] M. Aigner, On the linegraph of a directed graph, Math. Z. 102 (1967) 56–61. [2] C. Balbuena, A. Carmona, J. Fàbrega, M.A. Fiol, Superconnectivity of bipartite digraphs and graphs, Discrete Math. 197–198 (1999) 61–75. [3] C. Balbuena, P. García-Vázquez, A. Hansberg, L.P. Montejano, On the super-restricted arc-connectivity of s-geodetic digraphs, Networks (in press). [4] C. Balbuena, I. Pelayo, J. Gómez, On the superconnectivity of generalized p-cycles, Discrete Math. 255 (2002) 13–23. [5] F. Boesch, R. Tindell, Circulants and their connectivities, J. Graph Theory 8 (1984) 487–499. [6] Xing Chen, Juan Liu, Jixiang Meng, The restricted arc connectivity of Cartesian product digraphs, Inform. Process. Lett. 109 (2009) 1202–1205. [7] J. Fàbrega, M.A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (1989) 657–668. [8] J. Fàbrega, M.A. Fiol, Bipartite graphs and digraphs with maximum connectivity, J. Discrete Appl. Math. 69 (3) (1996) 269–278. [9] M.A. Fiol, On super-edge-connected digraphs and bipartite digraphs, J. Graph Theory 16 (1992) 545–555. [10] 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. [11] D. Geller, F. Harary, Connectivity in digraphs, Lecture Notes in Math. 186 (1970) 105–114. [12] J. Gómez, C. Padró, Perennes, Large generalized cycles, Discrete Appl. Math. 89 (1998) 107–123. [13] J. Gross, J. Yellen (Eds.), Handbook of Graph Theory, CRC Press, Boca Raton, FL, ISBN: 1-58488-090-2, 2003. [14] Y.O. Hamidoune, A property of α-fragments of a digraph, Discrete Math. 31 (1980) 105–106. [15] Y.O. Hamidoune, Sur les atomes d’un graphe orienté, abéliens, Discrete Math. 55 (1985) 323–326. [16] Y.O. Hamidoune, A.S. Lladó, O. Serra, Vosperian and superconnected abelian Cayley digraphs, Graphs Combin. 7 (1991) 143–152. [17] I. Pelayo, C. Balbuena, J. Gómez, On the connectivity of generalized p-cycles, Ars Combin. 58 (2001) 215–231. [18] S.M. Reddy, J.G. Kuhl, S.H. Hosseini, H. Lee, On digraphs with minimum diameter and maximum connectivity, in: Proceedings of the 20th Annual Allerton Conference, 1982, pp. 1018–1026. [19] L. Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett. 103 (2007) 234–239. [20] S. Wang, S. Lin, λ′-optimal digraphs, Inform. Process. Lett. 108 (2008) 386–389.