On the restricted connectivity and superconnectivity in graphs with given girth

On the restricted connectivity and superconnectivity in graphs with given girth夡 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, C/ Jordi Girona1i3, Edifici C2, E-08034 Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Avda Reina Mercedes 2, E-41012 Sevilla, Spain Received 7 March 2004; received in revised form 9 January 2006; accepted 11 July 2006 Available online 22 September 2006 Abstract The restricted connectivity (G) of a connected graph Gis defined as the minimum cardinality of a vertex-cut over all vertex-cuts Xsuch that no vertex uhas all its neighbors in X; the superconnectivity 1(G) is defined similarly, this time considering only vertices uin G−X, hence 1(G)⩽(G). The minimum edge-degree of Gis (G) =min{d(u) +d(v) −2:uv ∈E(G)},d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding 1(G)⩾(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31] and guaranteeing 1(G) = (G) = (G) under some additional constraints. Keywords: Superconnectivity; Restricted connectivity; Diameter; Girth 1. Introduction Throughout this paper, only undirected simple graphs without loops or multiple edges are considered. Let G=(V, E) be a graph with vertex set V=V (G) and edge set E=E(G).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}denotes the distance between Sand F. For every v∈Vand every nonnegative integer r⩾0, Nr(v) ={w∈V:d(w,v) =r}denotes the neighborhood of v at distance r.IfS⊂Vthen Nr(S) ={w∈ V:d(w,S) =r}, where d(w,S) means d({w},S). Observe that N0(S) =S. When r=1 we put simply N(v) and N(S) instead of N1(v) and N1(S).IfS⊂Vthen G[S]stands for the subgraph induced by S. The degree of a vertex vis d(v) =|N(v)|. Thus =(G) is the minimum degree over all vertices of G. The girth g=g(G) is the length of a shortest cycle in G. The diameter D=D(G) is the maximum distance over all pairs of vertices in G, and Gis connected if D<∞. Let Xbe a subset of vertices or edges. The notions of vertex-connectivity (G) and edge-connectivity (G) can be naturally generalized by imposing conditions on the components of G−Xand/or on the set X. Harary formulated 夡Research supported by the Ministry of Education and Science, Spain, 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.07.016 660 C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 in [8] the notion of conditional connectivity by imposing conditions on the components of G−X. Esfahanian and Hakimi in [4] introduced the restricted connectivity by imposing conditions on the set X. More precisely, a restricted cut X is a vertex-cut that belongs to the family of subsets of vertices F={X⊂V:N(u)Xfor any u∈V}. Provided that some restricted cut exists, the restricted connectivity is =(G) =min{|X|:Xis a restricted cut}. A restricted cut Xis called a -cut if |X|=.Arestricted edge-cut,the restricted edge-connectivity =(G) and a -cut are defined analogously. Later, Fàbrega and Fiol in [5,6] introduced the notion of -extraconnectivity by imposing that the resulting components of G−Xmust have at least +1 vertices, where ⩾1 is an integer. Therefore, a vertex-cut Xof Gis called an -extra cut if Xdoes not contain the neighborhood N(S)of any set Sof cardinality at most such that S∩X=∅. When =1, we have that any 1-extra cut must belong to the family F1={X⊂V:N(u)Xfor any u∈V\X}. Provided that some 1-extra cut exists, the 1-extraconnectivity is 1=1(G) =min{|X|:Xis a 1-extra cut}. A 1-extra cut Xis called a 1-cut if |X|=1.A1-extra edge-cut,the 1-extra edge-connectivity 1=1(G) and a 1-cut are defined analogously.The superconnectivity and edge-superconnectivity proposed in [2,3] can be measured by 1(G) and 1(G), respectively. A graph is superconnected, for short super-, if all its minimum vertex-cuts consist of the vertices incident with one vertex, see Boesch [2], Boesch and Tindell [3] and Fiol et al. [7]. Observe that a superconnected graph is necessarily maximally connected, (G) =(G), but the converse is not true (take Cg—a cycle of length g—with g⩾6 as a simple example of a maximally connected graph that is not superconnected). Notice also that 1(G) > (G) is a sufficient and necessary condition for Gto be superconnected. In a similar way an edge-superconnected or super- graph is defined. A connected graph Gis called -connected if (G) exists. From definitions it is clear that 1(G)=(G). Esfahanian and Hakimi [4] showed that each connected graph Gof order at least 4 except a star is -connected and satisfies (G)⩽(G), where (G) denotes the minimum edge-degree of G defined as (G) =min{d(u) +d(v) −2:uv ∈ E(G)}. Furthermore, a -connected graph is said to be -optimal if (G) =(G). Some of the authors in [1] have studied -optimality in graphs of diameter at most g−1, generalizing some results given by Hellwig and Volkmann [9] for graphs of diameter 2. For vertices the situation is different. When some restricted cut exists, it is clear that 1(G)⩽(G), since any restricted cut Xis certainly a 1-extra cut. The converse, however, is not always true. Fig. 1 provided in [4] is an example in which 1(G) =3=(G) +1 and (G) does not exist. Moreover, 1(G) does not exist for some graphs; this is the case for the complete bipartite graph Kn,m with n, m⩾2. We say that a connected graph Gis -connected if (G) exists, and 1-connected if 1(G) exists. We will show that Gis a -connected graph with (G)⩽(G) (thus, it is also 1-connected and 1(G)⩽(G)⩽(G)) whenever either g⩾6 and ⩾2, or g=5 and ⩾3. The same conclusion will be obtained when g=5 and =2, provided that Gsatisfies some additional requirement. In this paper we will restrict ourselves on graphs Gfor which the inequalities 1(G)⩽(G)⩽(G) hold. Fig. 1. Example provided in [4] by Esfahanian and Hakimi. C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 661 In relation to the lower-boundness of 1, some sufficient conditions on the diameter of a graph in terms of its girth were given in [7]: 1⩾2−2ifD⩽g−3(g odd); g−4(g even). (1) In this paper, we improve (1) by showing that a graph Gwith diameter at most g−3 satisfies 1(G)⩾(G). Next, we prove that this lower bound for 1(G) still holds for a graph with odd girth gimposing some additional constraint for all pair of vertices u, v at distance d(u, v)⩾g−2. Finally, we present sufficient conditions for a graph Gthat allow us to guarantee (G) =1(G) =(G). In Section 2 we present our results and prove them in Section 3. 2. Main results The first result provides a light requirement for a graph Gto be -connected with (G)⩽(G). Proposition 2.1. Let G be a connected graph with girth g⩾5and minimum degree ⩾2. Then G is -connected and (G)⩽(G) if one of the following assertions holds: (i) g⩾6or ⩾3. (ii) There exists some edge u0u1with d(u0)+d(u1)−2=(G) such that every cycle u0u1u2u3u4u0(if any)satisfies dG(u3)⩾3. In Proposition 2.1 of [1] some of the authors proved that the girth is a suitable index in order to study how far away a vertex of a non -optimal graph Gcan be from a set of vertices. Knowledge of this kind of structural properties is very useful when attempting to prove that Gis -optimal if the diameter satisfies D⩽g−2[1]. Thus, in order to obtain an improvement of known result (1) we need to show that the girth is also useful in order to study how far away a vertex of a 1-connected graph Gsatisfying 1(G) < (G) can be from a 1-cut. Now the main difficulty is to perform computations involving vertices instead of edges. Proposition 2.2. Let G=(V, E) bea1-connected graph with girth g and minimum degree ⩾2. Let X⊂Vbe a 1-cut. If 1(G) < (G) then for each connected component C of G−Xthere exists some vertex u∈V(C)such that d(u, X)⩾(g −3)/2. The following theorem shows that the minimum edge-degree of a graph Gis a lower bound for 1(G), whenever Gsatisfies certain constraints on the diameter and the minimum degree. Notice that this result is an improvement of known result (1). Theorem 2.3. LetGbea1-connected graph with girth g,minimum degree ⩾2and diameter D.Then 1(G)⩾(G) if D⩽g−3. Our next goal is to establish sufficient conditions to guarantee 1(G)⩾(G) in graphs Gof diameter g−2 for odd g. Theorem 2.4. LetGbea1-connected graph with odd girth g⩾5and minimum degree ⩾2. Then 1(G)⩾(G) if one of the following assertions holds: (i) Diameter is D=g−2and all pair u,vof vertices at distance d(u, v) =g−2is such that neither vertex unor v lies on a cycle of length g. (ii) |N(g−3)/2(u) ∩N(g−1)/2(v)|⩾3for all pair u,vof vertices at distance d(u, v)⩾g−2. Fig. 2 provides an example showing that Theorem 2.4 is best possible in the sense that the hypothesis |N(g−3)/2(u) ∩ N(g−1)/2(v)|⩾2 for all pair u, v of vertices at distance d(u, v)⩾g−2 with godd does not imply 1(G)⩾(G).Fig. 3 shows that the conditions in Theorem 2.4 yielding 1(G)⩾(G) are not necessary. 662 C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 Fig. 2. A graph with D=3, g=5, and 3 =1<=4. Fig. 3. 1=2=, even though the conditions of Theorem 2.4 do not hold. The following result shows that 1(G)⩾(G) if two distinct vertices in N(g−3)/2(u) ∩N(g−1)/2(v) satisfy certain requirement, for all pair u,vof vertices at distance d(u, v)⩾g−2 with godd. Theorem 2.5. LetGbea1-connected graph with odd girth g⩾7and minimum degree ⩾2. Suppose that for all pair u,vof vertices at distance d(u, v)⩾g−2the set N(g−3)/2(u) ∩N(g−1)/2(v) contains at least two distinct vertices x,y such that 2⩽d(x,y)⩽(g −3)/2and such that any w∈N(g−3)/2(v) ∩(N(x) ∪N(y))satisfies d(w,y)⩾(g −3)/2 if w∈N(x),d(w,x)⩾(g −3)/2if w∈N(y).Then 1(G)⩾(G). Noticing that any graph Gwith (G) =2 and 1(G)⩽(G) =2 cannot be superconnected, next corollary follows directly from Proposition 2.1, Theorems 2.3–2.5. Corollary 1. Let G be a connected graph with girth g⩾5, minimum degree ⩾2and diameter D.Suppose that there exists some edge u0u1such that d(u0)+d(u1)−2=(G) and every cycle u0u1u2u3u4u0(if any)satisfies dG(u3)⩾3. Then,1(G) =(G) =(G) if one of the following assertions holds: (i) D⩽g−3. (ii) gisodd,D=g−2, and all pair u,vof vertices at distance d(u, v) =g−2is such that neither vertex unor v lies on a cycle of length g. (iii) g is odd and |N(g−3)/2(u) ∩N(g−1)/2(v)|⩾3for all pair u,vof vertices at distance d(u, v)⩾g−2. (iv) g⩾7is odd,and for all pair u,vof vertices at distance d(u, v)⩾g−2the set N(g−3)/2(u)∩N(g−1)/2(v) contains at least two distinct vertices x,y such that 2⩽d(x,y)⩽(g−3)/2and such that any w∈N(g−3)/2(v)∩(N(x)∪N(y)) satisfies d(w,y)⩾(g −3)/2if w∈N(x),d(w,x)⩾(g −3)/2if w∈N(y). Furthermore,<1(G) =(G) =(G) if G also satisfies (G)⩾3. C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 663 3. Proofs Proof of Proposition 2.1. (i) Let uv be any edge of G. It is not difficult to see for all z∈V (G)\{u, v}that N(z)N({u, v})whenever g⩾6or⩾3. Hence N({u, v})is a restricted cut, following that Gis -connected and (G)⩽|N({u, v})|for any edge uv of G,so(G)⩽(G). (ii) Let u0u1be an edge satisfying the hypothesis of the proposition. Reasoning as in case (i) we have N(z)N({u0, u1})for any z∈N(u0)∪N(u1). So suppose that z/∈N(u0)∪N(u1)is such that N(z) ⊆N({u0,u 1}).Asno cycles of length 4 can exist we must have N(z) ={u4,u 2}with u4∈N(u0)−u1,u2∈N(u1)−u0, yielding a cycle u0u1u2zu4u0with dG(z) =2, against the hypothesis. Thus, Gis -connected. To end the proof, observe that (G)⩽|N({u0,u 1})|=d(u0)+d(u1)−2=(G). The following convention will be used henceforth. Let G=(V, E) be a graph and let X⊂V,v∈V\Xand u∈N(v). Let us introduce the sets S+ u(v) ={z∈N(v)−u:d(z,X) =d(v,X) +1}; S= u(v) ={z∈N(v)−u:d(z,X) =d(v,X)}; S− u(v) ={z∈N(v)−u:d(z,X) =d(v,X) −1}. (2) Clearly, S+ u(v),S= u(v) and S− u(v) form a partition of N(v)−u. Proof of Proposition 2.2. For g=3,4,5 the result is immediate. So suppose that g⩾6 and let Cbe any connected component of G−X. Let us denote by =max{d(u, X) :u∈V(C)}. First assume that =1. This implies that every vertex of V(C)is adjacent to some vertex of X.As|V(C)|⩾3, we can take an edge uv of E(C). Consider the sets defined in (2) and observe that S− v(u) ⊆X,S− u(v) ⊆Xand S+ v(u) =S+ v(u) =∅. Likewise, the sets S− v(u) ⊆X, S− u(v) ⊆X,N(S= u(v)) ∩Xand N(S= v(u)) ∩Xare pairwise disjoint because g⩾6. Therefore, as |N(S= u(v)) ∩ X|⩾|S= u(v)|and |N(S= v(u)) ∩X|⩾|S= v(u)|because g⩾6 and every vertex of V(C)is adjacent to some vertex of X, we have 1(G) =|X|⩾|S− v(u)|+|S− u(v)|+|S= v(u)|+|S= u(v)| =|N(u) −v|+|N(v)−u|=d(u) +d(v) −2⩾(G), which is a contradiction. Therefore we can assume that ⩾2. We reason by contradiction, so assume that 2⩽⩽ (g −3)/2−1, which implies that g⩾8. We study the following cases. Case 1: There exists an edge uv in Csuch that d(u, X) =d(v,X) =. In this case S+ u(v) =S+ v(u) =∅. Moreover, we have |N(S= u(v)) ∩X|⩾|S= u(v)|. Otherwise, by the Pigeonhole Principle there are two vertices v1,v 2∈S= u(v) both at distance to a vertex x∈N(S= u(v)) ∩X. Then there is a cycle going through {v1,v,v 2,x}of length at most 2+2⩽2(g −3)/2⩽g−2 which is impossible. In the same way it is proved that |N(v) ∩X|⩾|S− u(v)|. Furthermore, N(S= u(v)) ∩X,N(S= v(u)) ∩X,N(u) ∩Xand N(v) ∩Xare pairwise disjoint, because otherwise a cycle of length at most 2+3⩽g−1 exists. Therefore, we have 1(G) =|X|⩾|N(u) ∩X|+|N(v) ∩X|+|N(S= v(u)) ∩X|+|N(S= u(v)) ∩X| ⩾|S− v(u)|+|S− u(v)|+|S= v(u)|+|S= u(v)| =|N(u) −v|+|N(v)−u|=d(u) +d(v) −2=(G), against the hypothesis 1(G) < (G). Case 2: Every vertex uin Cwith d(u, X) =is such that d(v,X) =−1 for all v∈N(u). Let ube a vertex with d(u, X)=and consider u1∈N(u). Notice that d(u1,X)=−1 and every vertex in N(S+ u(u1)) is at distance −1 from X. Reasoning as in the previous case, we have the inequalities |N−1(N(S+ u(u1)) −u1)∩ X|⩾|N(S+ u(u1))−u1|⩾|S+ u(u1)|(since ⩾2), |N−1(S= u(u1))∩X|⩾|S= u(u1)|,|N−1(N(u)−u1)∩X|⩾|N(u)−u1|, and |N−1(u1)∩X|⩾|S− u(u1)|. Likewise, the sets N−1(N(S+ u(u1)) −u1)∩X,N−1(S= u(u1)) ∩X,N−1(u1)∩X 664 C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 and N−1(N(u) −u1)∩Xare pairwise disjoint. Hence we have 1(G) =|X|⩾|N−1(N(u) −u1)∩X|+|N−1(u1)∩X| +|N−1(S= u(u1)) ∩X|+|N−1(N(S+ u(u1)) −u1)∩X| ⩾|N(u) −u1|+|S− u(u1)|+|S= u(u1)|+|S+ u(u1)| =d(u) +d(u1)−2⩾(G), which is a contradiction. Therefore, we conclude that ⩾(g −3)/2. As a consequence of Proposition 2.2, if Gis a 1-connected graph with girth gsuch that 1(G) < (G) and Xis a 1-cut, then for any connected component Cof G−X, the following set is nonempty: CX={u∈V(C):d(u, X)⩾(g −3)/2}. Concerning this set we need to prove the following result. Lemma 1. Let G be a 1-connected graph with odd girth g⩾5and minimum degree ⩾2. Let X be a 1-cut and assume that there exists a connected component C of G−Xsuch that max{d(u, X) :u∈V(C)}=(g −3)/2. Then if 1(G) < (G),the following assertions hold: (i) The induced subgraph G[CX]contains edges. (ii) If u∈CXand N(u) ∩CX=∅then |N(u) ∩CX|⩾2. (iii) Any vertex u∈CXlies on a cycle of length g. (iv) There exists a vertex u in CXsuch that |N(g−3)/2(u) ∩X|=1. Proof. (i) When g=5, for every vertex u∈CXthere must exist some v∈N(u) such that v∈CX, that is, d(u, X) =d(v,X) =1; otherwise, N(u) ⊆X, against the fact that Xis a 1-extra cut. Hence assume g⩾7. We reason by contradiction supposing that every vertex u∈CXsatisfies N(u) ∩CX=∅. Hence d(u, X) =(g −3)/2 and |N(g−3)/2(u) ∩X|⩾d(u). Take u1∈N(u) and consider the sets defined in (2). Notice that d(u1,X)=(g −5)/2 and every vertex in N(S+ u(u1)) is at distance (g −5)/2 from X. Observe also that the sets N(g−5)/2(N(u) −u1)∩X, N(g−5)/2(u1)∩X,N(g−5)/2(S= u(u1)) ∩Xand N(g−5)/2(N(S+ u(u1)) −u1)∩Xare pairwise disjoint. Thus by the Pigeonhole Principle we have 1(G) =|X|⩾|N(g−5)/2(N(u) −u1)∩X|+|N(g−5)/2(u1)∩X| +|N(g−5)/2(S= u(u1)) ∩X|+|N(g−5)/2(N(S+ u(u1)) −u1)∩X| ⩾|N(u) −u1|+|S− u(u1)|+|S= u(u1)|+|N(S+ u(u1)) −u1|. As ⩾2, and taking into account the hypothesis, we have |N(S+ u(u1)) −u1|⩾|S+ u(u1)|which gives 1(G)⩾d(u) + d(u1)−2⩾(G), contradicting our assumption. (ii) It is equivalent to showing that S= u(v) =∅and S= v(u) =∅, for any edge uv of G[CX]. We reason by contradiction supposing that S= v(u) =∅. In this case, the sets N(g−3)/2(u) ∩X,N(g−3)/2(v) ∩Xand N(g−3)/2(S= u(v)) ∩Xare all of them pairwise disjoint (we take N(g−3)/2(S= u(v)) ∩X=∅in case S= u(v) =∅). Taking into account that |N(g−3)/2(u) ∩ X|⩾|S− v(u)|,|N(g−3)/2(v) ∩X|⩾|S− u(v)|and |N(g−3)/2(S= u(v)) ∩X|⩾|S= u(v)|,wehave 1(G) =|X|⩾|N(g−3)/2(u) ∩X|+|N(g−3)/2(v) ∩X|+|N(g−3)/2(S= u(v)) ∩X| ⩾|S− v(u)|+|S− u(v)|+|S= u(v)|=d(u) +d(v) −2⩾(G), and this is not possible. Hence S= u(v) =∅and S= v(u) =∅, for any edge uv of G[CX]. (iii) We reason by contradiction, so suppose that some vertex u∈CXdoes not lie on a cycle of length g. First, suppose that there exists some edge uv in G[CX]. Clearly, S+ v(u)=S+ u(v)=∅,S= v(u)=(N(u)−v)∩CXand S− v(u)=N(u)\CX. Notice that the sets N(g−3)/2(u) ∩X,N(g−3)/2(v) ∩X, and N(g−3)/2(S= v(u) ∪S= u(v)) ∩Xare pairwise disjoint because otherwise a cycle in Gof length at most g−1 would be found. Thus, we have 1(G) =|X|⩾|N(g−3)/2(u) ∩X|+|N(g−3)/2(v) ∩X|+|N(g−3)/2(S= v(u) ∪S= u(v)) ∩X|. C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 665 Since |N(g−3)/2(u) ∩X|⩾|S− v(u)|it follows that 1(G) =|X|⩾|S− v(u)|+|S− u(v)|+|N(g−3)/2(S= v(u) ∪S= u(v)) ∩X|. (3) Moreover, we have N(g−3)/2(S= v(u)) ∩N(g−3)/2(S= u(v)) ∩X=∅, because no cycle of length ggoes through u. Furthermore, |N(g−3)/2(S= v(u))∩X|⩾|S= v(u)|, because otherwise a cycle of length at most g−1 can be found; this fact together with (3) implies 1(G) =|X|⩾|S− v(u)|+|S− u(v)|+|S= v(u)|+|S= u(v)| =|N(u) −v|+|N(v)−u|⩾d(u) +d(v) −2, a contradiction. Second, suppose that N(u) ∩CX=∅. As discussed in (i) this assumption yields g⩾7 and every vertex of N(u) is at distance (g −5)/2 from X. Take u1∈N(u) and observe that the sets N(g−5)/2(N(u) −u1)∩X,N(g−5)/2(u1)∩X, N(g−5)/2(S= u(u1)) ∩X,N(g−5)/2((N(S+ u(u1)) −u1)\CX)∩Xand N(g−3)/2(N(S+ u(u1)) ∩CX)∩Xare all of them pairwise disjoint, because otherwise ulies on a cycle of length at most g, contradicting our assumption. Therefore, by the Pigeonhole Principle and taking into account that |N(S+ u(u1)) −u1|⩾|S+ u(u1)|because ⩾2, we have 1(G) =|X|⩾|N(g−5)/2(N(u) −u1)∩X|+|N(g−5)/2(u1)∩X| +|N(g−5)/2(S= u(u1)) ∩X|+|N(g−5)/2((N(S+ u(u1)) −u1)\CX)∩X| +|N(g−3)/2(N(S+ u(u1)) ∩CX)∩X| ⩾|N(u) −u1|+|S− u(u1)|+|S= u(u1)|+|N(S+ u(u1)) −u1| ⩾d(u) +d(u1)−2⩾(G), again a contradiction. (iv) Suppose that any vertex uin CXsatisfies |N(g−3)/2(u) ∩X|⩾2. Take any edge uv in G[CX]. Notice that S+ v(u) =S+ u(v) =∅and that the sets S= v(u),S− v(u),S= u(v) and S− u(v) are pairwise disjoint. The hypothesis implies |N(g−3)/2(S= u(v)) ∩X|⩾2|S= u(v)|and |N(g−3)/2(S= v(u)) ∩X|⩾2|S= v(u)|. We can assume |S= v(u)|⩽|S= u(v)|. Notice that the sets N(g−5)/2(S− v(u)) ∩X,N(g−3)/2(S= u(v)) ∩Xand N(g−5)/2(S− u(v)) ∩Xare pairwise disjoint, following that 1(G) =|X|⩾|N(g−5)/2(S− v(u)) ∩X|+|N(g−3)/2(S= u(v)) ∩X|+|N(g−5)/2(S− u(v)) ∩X| ⩾|S− v(u)|+2|S= u(v)|+|S− u(v)| ⩾|S− v(u)|+|S= u(v)|+|S= v(u)|+|S− u(v)| =|N(u) −v|+|N(v)−u|=d(u) +d(v) −2⩾(G), contradicting the hypothesis.  Proof of Theorem 2.3. The theorem is true when g=3,4, thus assume g⩾5. Suppose that 1(G) < (G) and consider two connected components, Cand Cof G−Xwhere Xisa1-cut. First assume that gis even. Then by Proposition 2.2 we have that there exists a vertex u∈V(C)such that d(u, X)⩾g/2−1 and there exists a vertex u∈V(C)such that d(X,u)⩾g/2−1. Hence D⩾d(u, u)⩾d(u, X) +d(X,u)⩾g−2, against the hypothesis D⩽g−3. Second assume that gis odd. By Proposition 2.2, we have that both sets CXand C Xare nonempty. For any u∈CX and any u∈C Xwe have g−3⩾D⩾d(u, u)⩾d(u, X)+d(X,u)⩾g−3. Hence d(u, u)=g−3 for any u∈CXand any u∈C X. Furthermore, max{d(u, X) :u∈V(C)}=(g −3)/2 and max{d(X,u):u∈V(C)}=(g −3)/2. Thus by Lemma 1, we can pick u∈CXsuch that N(g−3)/2(u) ∩X={x0}for some x0∈X, and we can pick u∈C Xsuch that N(g−3)/2(u)∩X={x 0}for some x 0∈X.Asd(u, u)=g−3, it follows that x0=x 0. Notice that N(u) ∩CX=∅, because otherwise |N(g−3)/2(u) ∩X|⩾|N(u)|⩾2. Take any v∈N(u) ∩CX. Since d(v,u)=g−3 we must have x0∈N(g−3)/2(v). As a consequence, the path from uto x0together with the path from vto x0and the edge uv form a cycle of length at most g−2, which is absurd.  Before proceeding with the proof of Theorem 2.4 we make the following remark, quoted without proof. 666 C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 Remark. Let Gbe a connected graph with odd girth gand diameter D⩾g−2. Then, each pair of vertices uand vat distance d(u, v)⩾g−2 satisfies |N(g−3)/2(u) ∩N(g−1)/2(v)|⩾1 if and only if D=g−2. Proof of Theorem 2.4. By Theorem 2.3, 1(G)⩾(G) if D⩽g−3. So taking into account the Remark we can suppose D=g−2 both in case (i) and (ii). Let Xbe an arbitrary 1-cut and let us assume that 1(G) < (G); hence by Proposition 2.2, the sets CXand C Xare nonempty for any two connected components Cand C of G−X. Case 1: Suppose d(X,u)⩾(g −1)/2 for some vertex uof C X. Let ube any arbitrary vertex in CX.As g−2=D⩾d(u, u)⩾d(u, X) +d(X,u)⩾d(u, X) +(g −1)/2⩾g−2, we obtain d(u, X) =(g −3)/2 for every u∈CX, that is, max{d(u, X) :u∈V(C)}=(g −3)/2. We further obtain that d(X,u)=(g −1)/2 and d(u, u) =g−2. (i) From the hypothesis of item (i) it follows that udoes not lie on a cycle of length gcontradicting Lemma 1 (iii). (ii) The hypothesis |N(g−3)/2(u) ∩N(g−1)/2(u)|⩾3 implies |N(g−3)/2(u) ∩X|⩾3 for every u∈CX, contradicting Lemma 1 (iv). Case 2: Suppose d(u, X) =d(X,u)=(g −3)/2 for any u∈CXand any u∈C X. By Lemma 1, we can take u∈CXsuch that N(g−3)/2(u) ∩X={x0}and we can take u∈C Xsuch that N(g−3)/2(u)∩X={x 0}. Notice that d(v,x0)=(g −1)/2 for any v∈N(u) ∩CXand d(v,x 0)=(g −1)/2 for any v∈N(u)∩C X. Let us show the following claim: Claim 1. Any two vertices w, w∈V (G) at distance d(w,w)⩾(g −1)/2satisfy |N(g−3)/2(w) ∩N(w)|⩽1. Otherwise we find s,t ∈N(g−3)/2(w) ∩N(w). Hence, the path from wto salong with the path from wto tand the edges swand twform a cycle of length at most g−1, a contradiction.  (i) By Lemma 1 we know that any vertex of CX∪C Xlies on a cycle of length g, then the hypothesis of item (i) implies d(w,w)=g−3 for every w∈CXand for every w∈C X. Therefore x0=x 0.Takeanyv∈N(u) ∩CX. Since d(v,u)=g−3 and N(g−3)/2(u)∩X={x 0}we must have x0=x 0∈N(g−3)/2(v), which is impossible because x0∈N(g−1)/2(v). (ii) First suppose d(u, u)=g−2, so x0= x 0and d(u, x 0)=(g−1)/2. Taking into account that N(g−3)/2(u)∩V(C)= ∅,N(g−3)/2(u) −x0⊆V(C), and |N(g−3)/2(u) ∩N(g−1)/2(u)|⩾3, we deduce that |N(g−3)/2(u) ∩N(g−1)/2(u)∩ V(C)|⩾2. But the hypothesis N(g−3)/2(u)∩X={x 0}allows us to deduce that N(g−3)/2(u) ∩N(g−1)/2(u)∩V(C)⊆ N(x 0)∩V(C), that is, |N(g−3)/2(u) ∩N(x 0)|⩾2 which contradicts Claim 1. Secondly suppose d(u, u)=g−3. As g−3=d(u, u)⩾d(u, X) +d(X,u)=g−3, it follows that x0= x 0and d(v,x0)=(g −1)/2 for any v∈N(u) ∩CXwhich implies by Claim 1 that |N(g−3)/2(v) ∩N(x0)|= 1. Moreover d(v,u)=g−2 for any v∈N(u) ∩CXand therefore, |N(g−3)/2(v) ∩N(g−1)/2(u)|⩾3. Notice that N(g−3)/2(v) ∩N(g−1)/2(u)=(N(g−3)/2(v) ∩N(g−1)/2(u)∩V(C))∪(N(g−3)/2(v) ∩N(g−1)/2(u)∩X) ⊆(N(g−3)/2(v) ∩N(x 0)∩V(C))∪(N(g−3)/2(v) ∩X) for any v∈N(u) ∩CX, since max{d(v,X) :v∈V(C)}=(g −3)/2 and N(g−3)/2(u)∩X={x 0}. Therefore, we have |N(g−3)/2(v) ∩X|⩾2 for any v∈N(u) ∩CX. (4) Notice that S= u(v) =∅by applying item (ii) of Lemma 1. Given w∈S= u(v), it is clear that d(w,x0)⩾(g −1)/2 and, therefore, d(w,u)=g−2. So, by hypothesis |N(g−3)/2(w) ∩N(g−1)/2(u)|⩾3 and reasoning as above we deduce that |N(g−3)/2(w) ∩X|⩾2 for any w∈S= u(v). (5) Thus, if u0∈N(u)∩CX, by (4) we have that |N(g−3)/2(v)∩X|⩾2 for any v∈S= u0(u) and by (5) |N(g−3)/2(w)∩X|⩾2 for any w∈S= u(u0). First suppose that |S= u0(u)|⩾|S= u(u0)|. Then, the sets N(g−3)/2(u) ∩X,N(g−3)/2(u0)∩Xand C. Balbuena et al. / Discrete Mathematics 307 (2007) 659 – 667 667 N(g−3)/2(S= u0(u)) ∩Xare pairwise vertex disjoint, and as a consequence we conclude that 1(G) =|X|⩾|N(g−3)/2(u) ∩X|+|N(g−3)/2(u0)∩X|+|N(g−3)/2(S= u0(u)) ∩X| ⩾|S− u0(u)|+|S− u(u0)|+2|S= u0(u)| ⩾|S− u0(u)|+|S− u(u0)|+|S= u0(u)|+|S= u(u0)| =d(u) +d(u0)−2⩾(G), a contradiction. Second, if |S= u(u0)|⩾|S= u0(u)|, then we apply the same reasoning to the pairwise vertex disjoint sets N(g−3)/2(u) ∩X,N(g−3)/2(u0)∩Xand N(g−3)/2(S= u(u0)) ∩X, obtaining again a contradiction.  Proof of Theorem 2.5. If D⩽g−3, then we are done by Theorem 2.3. Then, from the hypothesis and the Remark, we can assume henceforth D=g−2. Moreover, observe that if d(x,y) =2 it follows that there exists a vertex u∗∈N(g−5)/2(u) such that d(u∗,x)=d(u∗,y)=1 because otherwise a cycle of length g−1 would appear. In this case xxu∗yis a path of length 3 which is only possible if g=7,9 because of the hypothesis d(x,y)⩾(g −3)/2. Let us prove that |N(g−3)/2(u) ∩N(g−1)/2(v)|⩾3 holds for every u, v such that d(u, v) =g−2, hence the result will follow from Theorem 2.4. Suppose that u,vare two vertices satisfying d(u, v) =g−2 and N(g−3)/2(u) ∩N(g−1)/2(v) ={x,y}and we will arrive at a contradiction. Let xx···vand yy···vbe two paths of length (g −1)/2. Observe that x= y, since otherwise a cycle of length at most g−1 would be formed from the shortest (u, x)-path and (u, y)-path both of length (g −3)/2 and the edges xxand yx. Hence, {x,y}⊆N(g−3)/2(v) ∩N(g−1)/2(u). If some vertex z/∈{x,y} is assumed to be such that z∈N(g−3)/2(v) ∩N(g−1)/2(u), then zcannot be adjacent to a vertex in {x,y}, since otherwise a cycle of length at most g−1 appears; thus, zz···uis a path of length (g −1)/2, z/∈{x,y}. But, in this case, z∈N(g−3)/2(u) ∩N(g−1)/2(v), contradicting our initial assumption N(g−3)/2(u) ∩N(g−1)/2(v) ={x,y}.Asa consequence,N(g−3)/2(u) ∩N(g−1)/2(v) ={x,y}implies that N(g−3)/2(v) ∩N(g−1)/2(u) ={x,y},xxand yybeing two edges of G. Observe once more the fact that no cycle of length ⩽g−1 being able to exist implies that neither x nor xcan be adjacent to either yor y. By hypothesis d(x,y)⩽(g −3)/2 and d(x,y)⩽(g −3)/2, then both the shortest (x, y)-path and the shortest (x,y)-path are unique. Moreover, these two paths are vertex-disjoint because of the hypotheses d(x,y)⩾(g −3)/2 for any x∈N(x) ∩N(g−3)/2(v) and d(x,y)⩾(g −3)/2 for any y∈N(y) ∩N(g−3)/2(v). Thus these two paths together with the edges xx,yyform a cycle of length at most 2+d(x,y) +d(x,y)⩽g−1, which is a contradiction. Hence |N(g−3)/2(u) ∩N(g−1)/2(v)|⩾3 and the proof is over.  Acknowledgments The authors are specially grateful to the referees for their helpful comments. References [1] C. Balbuena, P. García-Vázquez, X. Marcote, Sufficient conditions for -optimality in graphs with girth g, J. Graph Theory 52 (2006) 73–86. [2] F.T. Boesch, Synthesis of reliable networks—a survey, IEEE Trans. Reliability 35 (1986) 240–246. [3] F.T. Boesch, R. Tindell, Circulants and their connectivities, J. Graph Theory 8 (4) (1984) 487–499. [4] A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. [5] J. Fàbrega, M.A. Fiol, Extraconnectivity of graphs with large girth, Discrete Math. 127 (1994) 163–170. [6] J. Fàbrega, M.A. Fiol, On the extraconnectivity of graphs, Discrete Math. 155 (1996) 49–57. [7] M.A. Fiol, J. Fàbrega, M. Escudero, Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31. [8] F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. [9] A. Hellwig, L. Volkmann, Sufficient conditions for -optimality in graphs of diameter 2, Discrete Math. 283 (2004) 113–120.