Connectivity of graphs with given girth pair

Connectivity of graphs with given girth pair夡 C. Balbuenaa, M. Cerab, A. Diánezb, P. García-Vázquezb, X. Marcotea aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Campus Nord, Edifici C2, C/Jordi Girona1i3, E-08034 Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avda Reina Mercedes 2, E-41012 Sevilla, Spain Received 19 October 2005; received in revised form 2 May 2006; accepted 25 June 2006 Available online 15 August 2006 Abstract Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209–218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g, h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g, h) such that g is odd and h⩾g + 3 is even has high (vertex-)connectivity if its diameter is at most h − 3. The edge version of all results is also studied. d. Keywords: Connectivity; Girth pair; Line graph 1. Introduction Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Unless otherwise stated, we follow [2] for terminology and definitions. Let G=(V, E) be a graph with vertex set V=V (G) and edge set E=E(G). For any S⊂V, the subgraph induced by S is denoted by G[S].Foru, v ∈V,d(u, v) =dG(u, v) denotes the distance between uand v; that is, the length of a shortest (u, v)-path. For S,F ⊂V,d(S,F) =dG(S, F ) =min{d(s,f) :s∈S,f ∈F}stands for the distance between Sand F. For every v∈Vand every integer r⩾0, Nr(v) ={w∈V:d(w,v) =r}denotes the neighborhood of vat distance r.IfS⊂V, then Nr(S) ={w∈V:d(w,S) =r}. When r=0, we have N0(S) =Sfor every subset Sof vertices, and when r=1 we put simply N(v) and N(S) instead of N1(v),N1(S). The degree of a vertex vis deg(v) =|N(v)|, whereas =(G) and =(G) stand for the minimum degree and the maximum degree over all vertices of G, respectively. The diameter D=D(G) is the maximum distance over all pairs of vertices in G. A graph Gis called connected if every pair of vertices is joined by a path; that is, if D<∞.IfS⊂Vand G−S is not connected, then Sis said to be a cut set. Certainly, every connected graph different from a complete graph has a cut set. A component of a graph Gis a maximal connected subgraph of G. A (noncomplete) connected graph is 夡This research was supported by the Ministry of Science and Technology, Spain, and the European Regional Development Fund (ERDF) under project MTM2005-08990-C02-02. E-mail addresses: [email protected] (C. Balbuena), [email protected] (M. Cera), [email protected] (A. Diánez), [email protected] (P. García-Vázquez), [email protected] (X. Marcote). 0012-365X/$ - see front matter doi:10.1016/j.disc.2006.06.024 156 C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 called k-connected if every cut set has cardinality at least k. The connectivity =(G) of a (noncomplete) connected graph Gis defined as the maximum integer ksuch that Gis k-connected. Observe that the minimum cut sets are those having cardinality . The connectivity of a complete graph K+1on +1 vertices is defined as (K+1)=. Connectivity has an edge analogue. An edge-cut in a graph Gis a set Wof edges of Gsuch that G−Wis nonconnected. Every connected graph on at least two vertices has an edge-cut. The edge-connectivity =(G) of a graph Gis the minimum cardinality of an edge-cut of G. Observe that the minimum edge-cuts are those having cardinality . Notice also that if Wis a minimum edge-cut of a connected graph G, then G−Wcontains exactly two components. A classic result due to Whitney is that ⩽⩽for every graph G. A graph is maximally connected if =, and maximally edge-connected if =. A graph is called -regular if all its vertices have the same degree . The odd girth (even girth)ofGis the length of a shortest odd (even) cycle in G. If there is no odd (even) cycle in G, then the odd (even) girth of Gis taken as ∞. Let g=g(G) denote the smaller of the odd and even girths of a graph G containing cycles, and let h=h(G) denote the larger. Then gis called the girth of G, and (g, h) is called the girth pair of G. Girth pairs were introduced by Harary and Kovács [4] and several interesting questions concerning girth pairs were posed in that paper. Now, in this paper we are interested in formulating sufficient conditions for a graph to have high connectivity in terms of the girth pair. In this regard, sufficient conditions for a graph with minimum degree to be maximally connected have been given in terms of its diameter Dand its girth g. Following these lines, next result is contained in [3,5]: =if D⩽2(g −1)/2, =if D⩽2(g −1)/2−1. (1) Notice that (1) tells us that any graph with odd girth gand diameter D⩽g−2 is maximally connected. In this paper we improve (1) for graphs with girth pair (g, h),godd and h⩾g+3 even, by means of the three following theorems. Theorem 1.1. Let G be a graph of minimum degree ⩾3and girth pair (g, h),g odd and h even with g+3⩽h<∞. The following assertions hold: (i) If the diameter is D⩽h−4, then (G) =. (ii) If D⩽h−3, then (G)⩾−1. (iii) If D⩽h−2and the maximum degree is ⩽2−3, then (G)⩾2. (iv) If g⩾5, the diameter of the line graph is D(LG)⩽h−3, and the maximum degree of G satisfies ⩽2−3, then (G) =. The last item of the above theorem is given in terms of the diameter of the line graph LG. Recall that in the line graph LG of a graph G, each vertex represents an edge of G, and two vertices are adjacent iff the corresponding edges are. Let us consider the edges x1y1,x 2y2∈E(G). It is widely known that the distance between the corresponding vertices of LG satisfies dLG(x1y1,x 2y2)=dG({x1,y 1},{x2,y 2})+1, (2) which is useful to prove that D(G) −1⩽D(LG)⩽D(G) +1. Theorem 1.2. Let G be a graph of minimum degree ⩾3and girth pair (g, h),g odd and h even with g+3⩽h<∞. The following assertions hold: (i) If the diameter is D⩽h−3, then (G) =. (ii) If D⩽h−2, then (G)⩾−1. (iii) If D⩽h−2and for all pairs of vertices at distance d(u, v) =h−2the induced subgraph G[N(h−2)/2(u) ∩ N(h−2)/2(v)]has edges,then (G) =. The previous results may be improved for regular graphs with girth pair (g, h), as we state in the following theorem. C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 157 x1 x2 y1 y2 u v Fig. 1. A 3-regular graph with g=5, h=8, D=6, and =2. Theorem 1.3. LetGbea-regular graph of degree ⩾3and girth pair (g, h),g odd and h even with g+3⩽h<∞. The following assertions hold: (i) If g⩾5and the diameter is D⩽h−3, then (G) =. (ii) If D⩽h−2, then (G)⩾2. (iii) If D⩽h−2and ⩾4is even,then (G) =. Fig. 1 depicts a 3-regular graph with g=5, h=8, D=6, and =2. This is a particular example showing that Theorem 1.2(ii) is best possible in the sense that the upper bound for the edge-connectivity cannot be enlarged when D⩽h−2. This example also states the necessity of some more additional hypotheses as those of Theorem 1.2(iii) (observe that N3(u) ∩N3(v) ={x2,y 1}in Fig. 1, vertices x2and y1being nonadjacent) or those of Theorem 1.3(iii) in order to guarantee =. The proofs of the above theorems need the following two results which roughly speaking show that his a suitable index to measure how far away a vertex of a nonmaximally connected graph with girth pair (g, h) can be from a cut set or an edge-cut. Proposition 1.4. Let G be a connected graph of minimum degree ⩾3and girth pair (g, h),g odd and h⩾g+3even. Let X be a cut set and C be any component of G−X.Then for every x∈Xthere exists some vertex u∈V(C)such that: (i) d(u, X)⩾(h −4)/2, |N(h−4)/2(u) ∩X|⩽1and x/∈N(h−4)/2(u),provided that|X|⩽−1. (ii) d(u, X)⩾(h −2)/2provided that |X|⩽−2. The following convention will be used to study the edge-connectivity. Let U,F ⊂V. Then [U,F]stands for the set of edges (if any) {uf ∈E:u∈U,f ∈F}.IfU={u}we write simply [u, F ]instead of [{u},F]. An arbitrary minimum edge-cut Swill be denoted by [V(C 1), V (C2)], where C1and C2are the only two components of G−S.We shall also write [V(C 1), V (C2)]=[X, Y ], where X⊂V(C 1)and Y⊂V(C 2)are the sets of end vertices of the edges of [V(C 1), V (C2)]. Proposition 1.5. Let G be a connected graph of minimum degree ⩾3and girth pair (g, h),g odd and h even with h⩾g+3. Let [V(C 1), V (C2)]=[X, Y ]be a minimum edge-cut with cardinality |[X, Y ]|⩽−1. Then for every edge 158 C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 xy ∈[X, Y ]with x∈Xand y∈Y,there exists some vertex u∈V(C 1)satisfying: (i) d(u, X)⩾(h −4)/2, |[N(h−4)/2(u) ∩X, Y ]|⩽1and xy /∈[N(h−4)/2(u) ∩X, Y ]. (ii) d(u, X)⩾(h −2)/2provided that |X|⩽−2. 2. Proofs The following result has been proved in [1,3,6,7]. Lemma 1 (Balbuena et al. [1], Fàbrega and Fiol [3], Soneoka et al. [6,7]).Let G be a connected graph with girth g and minimum degree .Let X be a cut set with |X|⩽−1and C be any component of G−X.Then there exists some vertex u∈V(C)such that d(u, X)⩾(g −1)/2. Our first objective is to study the vertex-connectivity of graphs Gwith girth pair (g, h),godd and h⩾g+3 even. From now on, we will use the following notation. Assume that X⊂Vis any cut set of Gwith cardinality |X|⩽−1. For every component Cof G−Xlet (C) =max{d(v,X) :v∈V(C)} and F(C) ={u∈V(C):d(u, X) =(C)}. From Lemma 1 it follows that if |X|<then (C)⩾(g −1)/2. (3) We begin with a result on the number (C) and the subset of vertices F(C). Lemma 2. Let G be a connected graph of minimum degree ⩾3and girth pair (g, h),g odd and h⩾g+3even. Let X be a cut set with |X|⩽−1and C be any component of G−Xsuch that (C)⩽(h −4)/2. Then |X|=−1and there exists some u∈F(C) such that |N(u)|=and |N(C)(u) ∩X|=1. Proof. Set =(C), and let us define r=min{|N(u) ∩X|:u∈F(C)},1⩽r⩽|X|⩽−1. Take any u0∈F(C) such that |N(u0)∩X|=rand let us see that N−1(v1)∩N−1(v2)∩X=∅for every two distinct vertices v1,v 2∈ N(u0)\F(C). This is clear if =1, so assume ⩾2 and let us suppose that x∈N−1(v1)∩N−1(v2)∩X. In this case a shortest (v1,x)-path, a shortest (v2,x)-path (both of length −1) and the edges u0v1and u0v2form an even cycle of length at most 2⩽h−4, which is impossible. Then we have |N(u0)|−|N(u0)∩F(C)|=|N(u0)\F(C)|⩽|N(u0)∩X|=r, (4) which implies that |N(u0)∩F(C)|⩾−r. Moreover, we have N(b) ∩N(c) ∩X=∅for every two distinct vertices b, c ∈N(u0)∩F(C), because otherwise an even cycle of length at most 2+2⩽h−2 is formed, which is impossible. Therefore it follows: (−r)r⩽ b∈N(u0)∩F(C) |N(b) ∩X|⩽|X|⩽−1. (5) Expression (5) is only possible if r=−1orr=1. Suppose r=−1 and let us see that we arrive at a contradiction. Substituting this value in (5) all the inequalities become equalities, then we obtain |X|=−1, |N(u0)∩F(C)|=1 and |N(b) ∩X|=−1, where {b}=N(u0)∩F(C). Moreover, taking into account the definition of rwe have N(u) ∩X=Xfor every vertex u∈F(C). (6) Therefore |N(u) ∩F(C)|=1 and |N(u)|=hold for every vertex u∈F(C), because of (4) and (5). Furthermore, notice that ⩾2. Indeed, if =1, taking two adjacent vertices u, w ∈F(C),wehaveN(u) −w=N(w)−u=Xand C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 159 cycles of length four are formed because ⩾3. This is impossible, so ⩾2. Now let us denote by X={x1,x 2,...,x −1} and N(u0)={u1,u 2,...,u }in such a way that u∈F(C) and the (ui,x i)-paths (i =1,...,−1)have length −1. As ⩾3 there exists a vertex z∈N(u1)−u0not lying on the (u1,x 1)-path, which satisfies −2⩽d(z,X)⩽. First suppose that d(z,X) =d(z,xi)=−2 . Clearly i= 1 and considering the shortest (z, xi)-path, the shortest (ui,x i)-path (of length −1 by (6)) and the path zu1u0ui, we obtain an even cycle of length at most 2⩽h−4, which is an absurdity. Secondly, if d(z,X) =d(z,xi)=−1, then the shortest (z, xi)-path, the shortest (u,x i)-path (of length because u∈F(C)) and the path zu1u0udefine an even cycle of length at most 2+2⩽h−2, which is again an absurdity. Finally if d(z,X) =, then z∈F(C), and by (6) we get N(z) ∩X=X. Thus, by considering any xi∈Xwith i= 1, the shortest (z, xi)-path, the shortest (u0,x i)-path and the path zu1u0define an even cycle of length at most 2+2⩽h−2, which is not possible. Hence we have obtained a contradiction for every possible value of d(z,X), which allows us to conclude that r=−1 is not possible. Then r=1 and substituting this value in (5) we have |X|=−1 and |N(u0)|=. Proof of Proposition 1.4. To see item (i) assume |X|⩽−1. First, we prove by induction on n⩾1 the following claim: Claim :(C)⩾(g +2n−3)/2whenever h⩾g+2n+1. For the induction start, let n=1. Then h⩾g+3, and by (3) we directly have (C)⩾(g −1)/2. Now, let n⩾2 and suppose that h⩾g+2n−1 yields (C)⩾(g +2n−5)/2. Assume next that h⩾g+2n+1, then (C)⩾(g +2n−5)/2 by hypothesis of induction. Suppose (C) == (g +2n−5)/2⩽(h −6)/2 and we will arrive at a contradiction. From Lemma 2 we have |X|=−1 and there exists some u∈F(C) such that |N(u)|=and |N(u) ∩X|=1. This in particular gives |N(u) ∩F(C)|=−1. Besides, N(w) ∩N(w)∩X=∅for every two distinct vertices w, w∈N(u) ∩F(C) because otherwise the graph would contain even cycles of length at most 2+2=g+2n−3⩽h−4, which is impossible. This implies |N(w) ∩X|=1 for each w∈N(u) ∩F(C) and therefore, |N(z)∩F(C)|⩾−1 for every z∈{u}∪(N(u) ∩F(C)). Let us see that |N2(u) ∩F(C)|⩾|N(u) ∩F(C)|⩾−1. (7) This is clear if g⩾5. It is also easy to see that the assertion (7) is true if g=3 and ⩾4. Otherwise the induced subgraph G[{u}∪(N(u) ∩F(C))]would contain a cycle of length four. Thus assume =g=3 and |N2(u) ∩F(C)|⩽1. Then G[{u}∪(N(u) ∩F(C))]is a triangle. But in this case |X|=2 and one x∈Xmust be at distance from two distinct vertices of the triangle, so we obtain an even cycle of length 2+2<h, which is a contradiction. Therefore assertion (7) is valid. Note that for all v∈N2(u) ∩F(C) we have N(v) ∩N(u) ∩X=∅because 2+2<h. Also any two distinct vertices v,v∈N2(u) ∩F(C) satisfy N(v) ∩N(v)∩X=∅, since otherwise taking into account that vand v are joined by a path of length four, then an even cycle of length at most 2+4<his formed, which is impossible. Therefore ⩽|N2(u) ∩F(C)|+1⩽ v∈N2(u)∩F(C) |N(v) ∩X|+|N(u) ∩X|⩽|X|=−1, which is an absurdity. As a consequence we conclude that (C) =⩾(g +2n−3)/2, completing the proof of the claim. Now, to follow with the proof of item (i) we may write h=g+2n+1 for some integer n⩾1, and by Claim we have (C) =⩾(g +2n−3)/2=(h −4)/2. Clearly, item (i) is valid for (C)>(h −4)/2, so assume that (C) =(h −4)/2. By Lemma 2 it follows that |X|=−1 and there exists a vertex u∈F(C) such that |N(u)|= and |N(h−4)/2(u) ∩X|=1. Let N(h−4)/2(u) ∩X={xu}. Obviously item (i) holds for every x∈X−xu. Taking into account that |N(u) ∩F(C)|=−1⩾2 and N(h−4)/2(w) ∩N(h−4)/2(w)∩X=∅for every two distinct vertices w, w∈N(u) ∩F(C), we conclude that there exists w∈N(u) ∩F(C) such that |N(h−4)/2(w) ∩X|=1 and xu/∈N(h−4)/2(w) ∩X. Item (ii) follows directly from item (i) and Lemma 2, because if (C) =(h −4)/2, then |X|=−1.  As a consequence of Lemma 2 and Proposition 1.4 we obtain the following corollary which will be very useful in the proof of our theorems. 160 C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 Corollary 1. Let G be a connected graph of minimum degree ⩾3and girth pair (g, h),g⩾5odd and h⩾g+3 even. Let X be a cut set with |X|⩽−1and C be any component of G−Xsuch that (C) =(h −4)/2. Then |N(x)∩V(C)|⩾−1for every x∈X. Proof. From Lemma 2 it follows that |X|=−1 and there exists a vertex u∈V(C)of degree such that d(u, X) = (h−4)/2 and N(h−4)/2(u)∩X={xu}, which means |N(u)∩F(C)|=−1. Moreover N(h−4)/2(v)∩N(h−4)/2(v)∩X=∅ for every two distinct vertices v,v∈N(u) ∩F(C). As a consequence N(h−4)/2(v) ∩X={xv}for every v∈ N(u) ∩F(C), which implies N(h−2)/2(u) ∩X=X−xu. By the same reason we have N(h−4)/2(v) ∩X={xv} N(h−2)/2(v) ∩X=X−xvfor every v∈N(u) ∩F(C). (8) Now, let x∈Xbe some given vertex, and suppose that (8) is written for a vertex u∈F(C) that has been chosen so that xu= x, according to Proposition 1.4. Let us consider the subset of vertices A={v∗∈N2(u) ∩F(C) :d(v∗,x)=(h −4)/2}. Let us see that |A|⩾−1. Indeed, as ⩾3, for every v∈N(u)∩F(C) there must exist some v∗∈(N(v)∩F(C))−u such that d(v∗,x)=(h −4)/2, by taking into account that |N(v)∩F(C)|=−1, |X|=−1, and xu= x. Moreover, v∗/∈N(u) ∩F(C) because g⩾5, then v∗∈A. Observe also that v∗= w∗for any two distinct vertices v,w ∈ N(u) ∩F(C), since otherwise we get a cycle of length four. Hence we conclude that |A|⩾|N(u) ∩F(C)|=−1. Furthermore, for any two vertices v,w ∈N(u)∩F(C), the shortest (v∗,x)and (w∗,x)-paths (both of length (h−4)/2) must be internally disjoint, for if not an even cycle (defined by these paths and the path v∗vuww∗of length four) of length at most (h −6)/2+(h −6)/2+4=h−2 is formed, an absurdity. Hence |N(x) ∩V(C)|⩾|A|⩾−1 for every x∈X. Proof of Theorem 1.1. Let Xbe a minimum cut set with |X|=(G)⩽−1 and let Cand Cbe two components, of G−X. (i) Suppose |X|=(G)⩽−1. Then by Proposition 1.4 there exist u∈V(C)and u∈V(C)such that d(u, X)⩾ (h−4)/2, d(u,X)⩾(h−4)/2, and N(h−4)/2(u)∩N(h−4)/2(u)∩X=∅.Thus D⩾d(u, u)⩾d(u, X)+1+d(X,u)⩾h− 3, against the hypothesis D⩽h−4. Hence (G) =. (ii) Suppose that |X|=(G)⩽−2. Then by Proposition 1.4 there exist u∈V(C) and u∈V(C)such that d(u, X)⩾(h −2)/2 and d(u,X)⩾(h −2)/2. Thus D⩾d(u, u)⩾d(u, X) +d(X,u)⩾h−2, again a contradiction. Therefore (G)⩾−1. (iii) Assume (G) =1 and let us consider a vertex cut X={x}. Then by item (ii) we can suppose that D=h−2. By Proposition 1.4 there exist u∈V(C) and u∈V(C)such that d(u, x)⩾(h −2)/2 and d(u,x)⩾(h −2)/2. Hence h−2=D⩾d(u, u)⩾d(u, x) +d(x,u)⩾h−2, and so (C) =(C)=(h −2)/2. Let u∈V(C)be a vertex for which d(u, x) =(h −2)/2. Notice that |N(u) ∩F(C)|⩾|N(u)|−1 holds, since otherwise |N(u)\F(C)|⩾2 and we would have an even cycle of length at most h−2 through x,u, and two vertices in N(u)\F(C). Moreover, for any two vertices v,w ∈N(u) ∩F(C), the shortest (v, x)-path and the shortest (w, x)-path (both of length (h −2)/2) must be internally disjoint, for if not an even cycle of length at most h−2 would again appear through vertex u. Therefore, there exist |N(u)|−1 internally disjoint shortest paths from N(u) ∩F(C) to vertex x, which implies that |N(x) ∩V(C)|⩾|N(u)|−1⩾−1. As we can proceed similarly for the other component C, we get deg(x)⩾|N(x)∩V(C)|+|N(x)∩V(C)|⩾2(−1)contradicting that the maximum degree of Gis at most 2−3. As a consequence, (G)⩾2 follows. (iv) Finally, assume that D(LG)⩽h−3 and (G) < . By applying Proposition 1.4 we have (C)⩾(h −4)/2 and (C)⩾(h−4)/2. If (C)=(C)=(h−4)/2, then from Corollary 1 it follows for every x∈Xthat |N(x)∩V(C)|⩾−1 and |N(x) ∩V(C)|⩾−1. This implies |N(x)|⩾2−2>, because ⩾3, which is impossible as the maximum degree of the graph is at most 2−3. Hence we may assume (C)⩾(h −2)/2. Let us see that Ccontains an edge uv in such a way that u, v are at distance at least (h −2)/2 from X. This is clear if (C)⩾h/2 so assume (C) =(h −2)/2. If every neighbor of uis at distance (h −4)/2 from X, we could find even cycles of length h−2 passing through two distinct neighbors of uand some vertex of X, which is impossible. We conclude that if (C)⩾(h −2)/2 there exists an edge uv in Csuch that dG({u, v},X)⩾(h −2)/2. C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 161 If (C)⩾(h −2)/2 we can consider an edge uvin Csuch that dG({u,v},X)⩾(h −2)/2. Then by using (2) we have h−3⩾D(LG)⩾dLG(uv, uv)=dG({u, v},{u,v})+1 ⩾dG({u, v},X)+dG(X, {u,v})+1 ⩾h−1, again a contradiction. Hence we may assume (C)=(h −4)/2, and by applying Lemma 2 we can take an edge uv in Csuch that dG({u,v},X)=(h −4)/2. In this case we have h−3⩾D(LG)⩾dLG(uv, uv)=dG({u, v},{u,v})+1 ⩾dG({u, v},X)+dG(X, {u,v})+1 ⩾h−2, which is again an absurdity. Therefore (G) =. Our final goal is to study the edge-connectivity of graphs with girth pair (g, h). For edges there is an analogous known result to Lemma 1. Lemma 3 (Balbauena et al. [1], Fàbrega and Foil [3], Soneoka et al. [6,7]).Let G be a connected graph with girth g and minimum degree .Let [V(C 1), V (C2)]=[X, Y ]be a minimum edge-cut. Then there exists some vertex u∈V(C 1) such that d(u, X)⩾(g −1)/2if |X|⩽−1. Next, we improve this result for graphs with girth pair (g, h),godd and heven with h⩾g+3. This is done by means of Proposition 1.5, whose proof follows. Proof of Proposition 1.5. Let us see first that Xand Yare cut sets of G. Suppose that X=V(C 1).As|X|⩽|[X, Y ]|⩽ −1, then every x∈Xmust be adjacent to at least two vertices inY. Hence for any vertex u∈Xwe have |N(u)∩X|>0 and |[X, Y ]|⩾|[u, Y ]| +  x∈N(u)∩X |[x,Y]|⩾|N(u) ∩Y|+2|N(u) ∩X|>|N(u)|⩾, a contradiction. Therefore X= V(C 1)and Y= V(C 2), which means that both XandYare cut sets of cardinality at most −1. Then, observe that item (ii) follows directly from Proposition 1.4. For item (i) let Cbe a component of C1−X.By Proposition 1.4 we have (C)⩾(h −4)/2. Notice that if (C)⩾(h −2)/2 we are done, so assume (C) =(h −4)/2. Then by Lemma 2, |X|=−1 and there exists a vertex u∈F(C) such that N(h−4)/2(u) ∩X={xu}. This implies that |[x,Y]| = 1 for any x∈X, since |[X, Y ]| = −1 because |[X, Y ]|⩾|X|=−1. Hence [N(h−4)/2(u) ∩X, Y ]={xuy} for some y∈Y. Obviously item (i) holds for every xy∈[X, Y ]−xuy. Taking into account that |N(u)∩F(C)|=−1 and N(h−4)/2(w) ∩N(h−4)/2(w)∩X=∅for every two distinct vertices w, w∈N(u) ∩F(C), we conclude that there exists w∈N(u) ∩F(C) such that |[N(h−4)/2(w) ∩X, Y ]|=1and xuy/∈[N(h−4)/2(w) ∩X, Y ]. Proof of Theorem 1.2. As a consequence of Proposition 1.5 we obtain the first two items (i) and (ii) of Theorem 1.2. The proof of these items is straightforward and similar to that of items (i) and (ii) of Theorem 1.1, hence the details are omitted. To prove item (iii) notice that (G)⩾−1 by (ii). Let us suppose that (G) =−1 and we will arrive at a contradiction. Let [V(C 1), V (C2)]=[X, Y ]be a minimum edge-cut with cardinality |[X, Y ]|=−1. Case 1: Suppose |Y|⩽−2. Then by Proposition 1.5 there exists a vertex v∈V(C 2)such that d(v,Y)⩾(h − 2)/2. Let ube any arbitrary vertex in F(C1). Taking into account that |X|⩽−1, from Proposition 1.5 we have h−2⩾D⩾d(u, v)⩾d(u, X) +1+d(v,Y)⩾(h−4)/2+1+(h−2)/2=h−2. Thus d(u, X) =(h −4)/2, d(v,Y)= (h −2)/2 and d(u, v) =h−2 for any u∈F(C1). By hypothesis the induced subgraph G[N(h−2)/2(u) ∩N(h−2)/2(v)] has edges, then we have |N(h−2)/2(u)∩N(h−2)/2(v)|⩾2. This implies that |[N(h−4)/2(u)∩X, Y ]|⩾2 which contradicts item (i) of Proposition 1.5. 162 C. Balbuena et al. / Discrete Mathematics 307 (2007) 155 – 162 Case 2: Suppose |X|=|Y|=−1. In this case each vertex of Xis adjacent to one unique vertex ofYand each vertex ofY is adjacent to one unique vertex of X. Following Proposition 1.5, there exist two vertices u∈V(C 1)and v∈V(C 2)such that d(u, X)⩾(h−4)/2 and d(v,Y)⩾(h−4)/2. If either d(u, X)⩾(h−2)/2ord(v,Y)⩾(h−2)/2 for some u, v, the proof follows as in Case 1. So suppose d(u, X)=d(v,Y)=(h−4)/2 for all u∈F(C1)and v∈F(C2). Proposition 1.5 allows us to choose vertices uand vin such a way that [N(h−4)/2(u) ∩X, Y ]={xuy}and [X, N(h−4)/2(v) ∩Y]={xyv}, with x= xuand y= yv. Therefore, we have d(u, v) =h−2 and N(h−2)/2(u) ∩N(h−2)/2(v) ={x,y}. By hypothesis the graph contains the edge xy which is a contradiction because xis only adjacent to yvand y= yv. Proof of Theorem 1.3. (i) Assume D⩽h−3 and (G) < . Then from Theorem 1.1 it follows that D=h−3 and any minimum cut set Xhas |X|=(G) =−1. Let us consider any two components Cand Cof G−X.By Proposition 1.4 we have h−3=D⩾(C) +(C)⩾h−4, so we deduce that there exists at most one component C∗ with (C∗)=(h −2)/2 and every other different component Cof G−Xmust satisfy (C) =(h −4)/2. Let Cbe a component with (C)=(h−4)/2. Taking into account that Gis -regular, by Corollary 1 we have |N(x)∩V(C)|=−1 for every x∈X, which implies that there exists one only component C= Cin G−Xwith |N(x)∩V(C)|=1. Thus the set of edges [X, V (C)]has cardinality |X|=−1 and is an edge-cut, which contradicts Theorem 1.2 because D=h−3. (ii) (G)⩾2 for D⩽h−2 is a direct consequence of item (iii) of Theorem 1.1. (iii) By Theorem 1.2 we know that (G)⩾−1. Suppose that (G) =−1 and we will arrive at a contradiction. Let [V(C 1), V (C2)]=[X, Y ]be a minimum edge-cut with cardinality |[X, Y ]|=−1. Then |X|⩽−1 and |Y|⩽−1 and by Proposition 1.4 there exist u∈V(C 1)and v∈V(C 2)such that d(u, X)⩾(h −4)/2 and d(v,Y)⩾(h −4)/2. So, we have h−2⩾D⩾d(u, v)⩾d(u, X)+1+d(v,Y)⩾(h−4)/2+1+(h−4)/2=h−3. Without loss of generality we may assume (C1)=(h −4)/2. By Lemma 2 we have |X|=−1, which implies |N(x)∩V(C 1)|=−1 for all x∈Xby Corollary 1. But then the number of vertices of odd degree (−1) in the component C1is odd (−1) which is impossible. Hence, (G) =and the result holds.  References [1] M.C. Balbuena, A. Carmona, J. Fàbrega, M.A. Fiol, On the order and size of s-geodetic digraphs with given connectivity, Discrete Math. 174 (1997) 19–27. [2] G. Chartrand, L. Lesniak, Graphs and Digraphs, fourth ed., Chapman & Hall, London, UK, 2005. [3] J. Fàbrega, M.A. Fiol, Maximally connected digraphs, J. Graph Theory 13 (3) (1989) 657–668. [4] F. Harary, P. Kovács, Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209–218. [5] M. Imase, T. Soneoka, K. Okada, Connectivity of regular directed graphs with small diameter, IEEE Trans. Comput. C-34 (1985) 267–273. [6] T. Soneoka, H. Nakada, M. Imase, Sufficient conditions for dense graphs to be maximally connected, Proceedings of ISCAS85, 1985, pp. 811–814. [7] T. Soneoka, H. Nakada, M. Imase, C. Peyrat, Sufficient conditions for maximally connected dense graphs, Discrete Math. 63 (1987) 53–66.