Connectivity measures in matched sum graphs
Abstract
A matched sum graph G of two graphs G1 and G2 of the same order is obtained from the union of G1 and G2 and from joining each vertex of G1 with one vertex of G2 according to one bijection f between the vertices in V(G1) and V(G2). When G1 =G2 =H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H f . In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.
Full text
Connectivity measures in matched sum graphs夡 C. Balbuenaa, 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 Abstract A matched sum graph G of two graphs G1 and G2 of the same order is obtained from the union of G1 and G2 and from joining each vertex of G1 with one vertex of G2 according to one bijection f between the vertices in V(G1) and V(G2). When G1 =G2 =H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H f . In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities. . Keywords: Restricted edge-cut; Restricted cut; Connectivity; Conditional connectivity; Superconnectivity; Restricted connectivity 1. Introduction Let G=(V, E) be a simple graph with vertex set V=V (G) and edge set E=E(G). Throughout this paper, only undirected simple graphs without loops or multiple edges having at least two vertices are considered. For every S⊂V, the neighborhood of S denoted by N(S)=NG(S) is the set of vertices in V−Sthat are adjacent to some vertex in S, and let NG[S]=NG(S) ∪S. The degree of a vertex vis d(v) =dG(v) =|N(v)|, and =(G) is the minimum degree over all vertices of G. For every u∈V, the edge-neighborhood of u is (u) =G(u) ={e∈ E:eis incident with u}. For every uv ∈E, the edge-boundary of uv denoted by (uv) =G(uv) is the set of edges (uv) =((u) ∪(v)) −uv, and |(uv)|=d(u) +d(v) −2 is called the edge-degree of uv. The minimum edgedegree of Gis denoted by =(G) =min{|(uv)|:uv ∈E}.Acut [edge-cut] of a connected graph Gis a set Sof vertices [edges] such that G−Sis not connected. The connectivity =(G) [edge-connectivity,=(G)]is the minimum cardinality of a cut [edge-cut], and it is widely known that (G)⩽(G)⩽(G). A connected graph Gis called maximally connected [maximally edge-connected]if(G) =(G) [(G) =(G)].Unless otherwise stated, we follow [8] for additional terminology and definitions. 夡Research supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2005-08990-C02-02. E-mail addresses: [email protected] (C. Balbuena), [email protected] (P. García-Vázquez), francisco.javier[email protected] (X. Marcote). doi:10.1016/j.disc.2007.04.051
1986 C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 Two connected graphs with the same connectivity [edge-connectivity] may be considered to have different reliabilities, mainly due to the properties satisfied by either minimum cuts [edge-cuts] or the associated components. In this regard, Esfahanian and Hakimi [9] introduced two indices of connectivity by considering cuts or edge-cuts that satisfy some condition. More precisely, a cut [edge-cut] Xis called restricted if no vertex uof the graph is such that N(u) ⊆X [(u) ⊆X]; the restricted connectivity =(G) and the restricted edge-connectivity =(G) are then defined as =min{|X|:X⊂Vis a restricted cut}, =min{|X|:X⊂Eis a restricted edge-cut}. A few years later, Balbuena et al. [1] approached the reliability of a graph Gby considering cuts [edge-cuts] Xsuch that every component of G−Xhas at least two vertices. These P1-cuts [edge P1-cuts] were introduced following [10], in the context of the conditional connectivities formulated in [14]. Observe that a cut [edge-cut] XisaP1-cut [edge P1-cut] if no vertex u∈V−Xof the graph is such that N(u) ⊆X[no vertex u∈Vsatisfies (u) ⊆X]. The corresponding indices of connectivity 1=1(G) and 1=1(G) were defined as 1=min{|X|:X⊂VisaP1-cut}, 1=min{|X|:X⊂Eis an edge P1-cut}. The superconnectivity and edge-superconnectivity proposed in [5,6] can be measured by 1(G) and 1(G), respectively. A graph is superconnected if every minimum cut consists of the vertices adjacent to one vertex that does not belong to the cut; see Boesch [5], Boesch and Tindell [6], and Fiol et al. [11]. It is easy to see that a superconnected graph Gis necessarily maximally connected (but the converse is not true, as happens, for instance, for C6), and also that 1(G) > (G) is a necessary and sufficient condition for Gto be superconnected, provided that 1(G) can be defined. In a similar way, the concept of an edge-superconnected graph can be introduced. There are obvious similarities between the pairs of indices (G),(G) and 1(G),1(G). Indeed, 1(G)=(G),but 1(G)⩽(G), because any restricted cut is a P1-cut (however, the converse is not true, as shown in [9]). These indices are well defined whenever some specific type of cut or edge-cut exists. In this respect, it was shown [9] that (G) exists if Gis not a star and its order is at least 4, and (G)⩽(G). The situation for vertices seems much more complicated. Neither (G) nor 1(G) exists for a number of graphs G. Even though to our knowledge no characterization of graphs for which either (G) or 1(G) exists has been given, one can assure the existence of these indices for some families of graphs. For instance, it is easy to see that both (G) and 1(G) exist for all those graphs of girth g⩾5 and minimum degree ⩾3, or those of girth g⩾6 (observe that N({u, v})is a restricted cut for every edge uv), all of these satisfying 1(G)⩽(G)⩽(G). A graph Gis -connected [-connected]if(G) [(G)]exists, and is said to be -optimal [-optimal]if(G) =(G) [(G) =(G)]. Some sufficient conditions for a graph to be -optimal and -optimal have been given in terms of the girth [2,3]. In this paper, we are interested in providing lower bounds on the connectivities ,,1,for matched sum graphs. Matched sum graphs were introduced by Georges and Mauro [12] as follows. Given two graphs G1,G2of the same order |V(G 1)|=|V(G 2)|, and a matching Mfrom V(G 1)to V(G 2), the matched sum graph of G1and G2, denoted by G1M+G2, is the graph with V(G 1M+G2)=V(G 1)∪V(G 2)and E(G1M+G2)=E(G1)∪E(G2)∪M. Since the matching Mcan be written by means of a bijection f:V(G 1)→V(G 2)as M={xf (x) :x∈V(G 1)}, it may be useful to denote alternately a matched sum graph G1M+G2by G1∪fG2. Matched sum graphs constitute a generalization of permutation graphs, which were introduced by Chartrand and Harary in [7]. Indeed, when G1=G2=H, any bijection f:V(H)→V(H)is a permutation of V(H), and the corresponding matched sum graph H∪fHis the permutation graph Hf. Examples of permutation graphs include hypercubes, prisms and some generalized Petersen graphs. See [4,13,15,17,18] for results and properties on permutation graphs. This paper is devoted to study how connected matched sum graphs are. For the considered matched sum graphs G1∪fG2, it must be emphasized that G1and G2need not be isomorphic, contrarily to the case of permutation graphs. In Section 2, we present our results and we provide the details of the proofs in Section 3. 2. Main results Let G1and G2be two graphs such that |V(G 1)|=|V(G 2)|, and fany bijection from V(G 1)to V(G 2). Clearly, G1 and G2connected yield a connected matched sum graph G=G1∪fG2.
C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 1987 e1 e2 e3 Fig. 1. The set {e1,e 2,e 3}is a minimum restricted edge-cut. Theorem 2.1. Let G1and G2be two connected graphs of the same order |V(G 1)|=|V(G 2)|and minimum degrees (G1)⩾2, (G2)⩾2. Then for any bijection f from V(G 1)to V(G 2),the following assertions hold for the matched sum graph G=G1∪fG2: (i) (G) =min{(G1)+1,(G2)+1}. (ii) min{(G1)+2,(G2)+2,(G1)+(G2)}⩽(G)⩽min{(G1)+2,(G2)+2}. (iii) min{(G1)+(G2), (G)}⩽(G)⩽(G). (iv) min{(G1)+(G2), (G)}⩽(G)⩽(G). As an immediate consequence of Theorem 2.1 we obtain the following results concerning the connectivity and edge-connectivity of permutation graphs which were already proved by Lai in [15]. Recall that the permutation graph Hcan be written as H∪H, where :V(H)→V(H)is a permutation. Corollary 1 (Lai [15]).For all graphs H and permutations : min{2(H ), (H) +1}⩽(H )⩽(H) +1, min{2(H ), (H) +1}⩽(H )⩽(H) +1. Next, we study the restricted edge-connectivity of matched sum graphs G=G1∪fG2when G1and G2are both connected and have minimum degrees (G1)⩾2, (G2)⩾2, respectively. For the simplest case, |V(G 1)|=|V(G 2)|=3, each Gimust be a triangle, and it is easily seen that all possible matched sum graphs G=G1∪fG2are isomorphic, and they are not -optimal since (G) =3<4=(G) (see Fig. 1, where {e1,e 2,e 3}is the matching corresponding to a bijection f:V(G 1)→V(G 2)). Thus, we assume |V(G 1)|=|V(G 2)|⩾4. Theorem 2.2. Let G1and G2be two connected graphs of the same order |V(G 1)|=|V(G 2)|⩾4, and minimum degrees (G1)⩾2, (G2)⩾2. Then for any bijection f from V(G 1)to V(G 2),the graph G=G1∪fG2is -connected and min{(G1)+(G2), (G1)+(G1), (G2)+(G2), |V (G)|/2,(G)}⩽(G)⩽(G). Let G1and G2be two graphs of minimum degrees (G1)⩾(G2)⩾2 such that |V(G 1)|=|V(G 2)|⩾min{(G1)+ 2,(G2)+2}. Then from Theorem 2.1, it follows that |V(G 1)|=|V(G 2)|⩾(G)⩾4. If we assume (Gi)⩾(Gi)− (Gi)+2 for both i=1,2, then (G1)+(G2)⩾((G1)−(G1)−(G2)+2)+(G2)+2⩾((G1)−(G2)) + (G2)+2⩾(G), where the inequality (G1)⩾2(G1)−2 has been taken into account. Hence the next corollary follows as a consequence of Theorem 2.2. Corollary 2. Let G1and G2be two connected graphs of minimum degrees (G1)⩾2, (G2)⩾2, the same order |V(G 1)|=|V(G 2)|⩾min{(G1)+2,(G2)+2},and satisfying (Gi)⩾(Gi)−(Gi)+2for both i=1,2. Then, for any bijection f from V(G 1)to V(G 2),the graph G=G1∪fG2is -optimal. Observe that both graphs G1and G2have been assumed to be maximally edge-connected in the above result, since (Gi)⩾(Gi)−(Gi)+2⩾(Gi)implies easily that (Gi)=(Gi). The following corollary shows that -optimality of a matched sum graph G1∪fG2can be guaranteed even if one of G1,G2is not maximally edge-connected. Corollary 3. Let G1and G2be two connected graphs of minimum degrees (G1),(G2)and the same order |V(G 1)|= |V(G 2)|⩾2∗,where ∗=min{(G1), (G2)}⩾2. Assume that (Gi)⩾∗for both i=1,2. Let f be any bijection from V(G 1)to V(G 2),and let G=G1∪fG2.Then,Gis-optimal and (G) =(G) =2(G) −2if any of the following
1988 C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 G1 G2 Fig. 2. Every matched sum graph G=G1∪fG2is -optimal (edges of the matching are not depicted). conditions holds: (i) (Gi)=2∗−2for i=1or i=2. (ii) (G1)=(G2)=∗,and f is such that dG2(f (x)) =dG1(x) =∗for some vertex x∈V(G 1). An application of point (i) of Corollary 3 may be seen in Fig. 2. Graph G1is not maximally edge-connected, because (G1)=3<4=(G1); graph G2(Petersen graph) satisfies (G2)=3=(G2).As∗=min{(G1), (G2)}=3 and (G2)=4=2∗−2, it turns out that for every bijection ffrom V(G 1)to V(G 2), the matched sum graph G=G1∪fG2 satisfies (G) =(G) =2(G) −2=6, hence Gis -optimal. From now on, we are going to approach the restricted connectivities (G),(G) and the superconnectivity 1(G) for triangle-free matched sum graphs G. Hence we only deal with graphs for which |G(uv)|=|NG({u, v})|holds for every edge uv. Thus, we can write (G) =min{|NG({u, v})|:uv ∈E(G)}. Theorem 2.3. Let G1and G2be two triangle-free connected graphs of the same order and minimum degrees (G1)⩾2, (G2)⩾2. Then for any bijection f from V(G 1)to V(G 2),the graph G=G1∪fG2is -connected and min{(G1)+ (G2), (G)}⩽(G)⩽(G). Observe that this result is an improvement of Theorem 2.2 for triangle-free graphs, at least for those cases where (G1)>(G2)(thus(G2)+(G2)<(G1)+(G2))or(G2)>(G1)(thatis,(G1)+(G1)<(G1)+(G2)). Notice also that the -optimality of the matched sum graph G=G1∪fG2is directly guaranteed by Theorem 2.3 whenever (G1)+(G2)⩾(G). Next, let us focus our attention on the (vertex-) connectivity parameters 1(G),(G). As pointed out in the introduction, for some graphs Gone can assure both the existence of these two indices and the chain 1(G)⩽(G)⩽(G), but a complete characterization of graphs for which these two statements hold has not been given yet. The following proposition gives four sufficient conditions in this regard for triangle-free graphs. Proposition 2.4. Let G be a connected triangle-free graph of minimum degree (G)⩾2. Then,Gis-connected and 1(G)⩽(G)⩽(G) if at least one of the following assertions holds: (i) The girth is g(G)⩾6.
C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 1989 (ii) (G)⩾3and the girth is g(G)⩾5. (iii) |V (G)|⩾(G)+3,and there exists an edge xy such that both |G(xy)|=(G) and |NG({x,y})∩NG(z)|⩽dG(z)−1 for any vertex z/∈{x,y}. (iv) Gis a matched sum graph,G=G1∪fG2,(G)⩾3, and no edge of the matching M={xf (x) :x∈V(G 1)} belongs to a cycle of length five. The following theorem may be seen as an improvement of item (iv) of Theorem 2.1. Indeed, we show that a matched sum graph Gof two triangle-free graphs Gi,i=1,2, might have 1(G) > (G)⩾(G1)+(G2), without any kind of requirement on 1(Gi),i=1,2. Theorem 2.5. Let G1and G2be two connected triangle-free graphs of the same order and minimum degrees (G1)⩾2, (G2)⩾2. Then for any bijection f from V(G 1)to V(G 2),the graph G=G1∪fG2is -connected and min{(G1)+ (G2), (G)}⩽1(G)⩽(G)⩽(G) if G satisfies any of the conditions (i), (ii), (iii) or (iv) in Proposition 2.4. Clearly, 1(G) =(G) =(G) holds for every matched sum graph G=G1∪fG2satisfying both the requirements in Theorem 2.5 and the constraint (G1)+(G2)⩾(G). Recall that NG[S]=NG(S) ∪Sfor every subset Sof vertices. Corollary 4. Let G1and G2be two connected triangle-free graphs of the same order and minimum degrees (G1)⩾3, (G2)⩾3. Let f be a bijection from V(G 1)to V(G 2),and let G=G1∪fG2.Then,for every vertex a∈V (G) such that dG(a)⩽(G) −2, the graph G−NG[a]is connected if (G1)+(G2)⩾(G) and G satisfies any of the conditions (i), (ii), (iii) or (iv) in Proposition 2.4. Corollary 5. Let G1and G2be two connected d-regular graphs,d⩾2, of the same order. Let f be a bijection from V(G 1)to V(G 2),let G=G1∪fG2,and suppose that the girth is g(G)⩾5. The following statements hold: (i) If (Gi)=dfor both i=1,2, then G is -optimal and (G) =(G) =2d. (ii) If (Gi)=dfor both i=1,2, then G is both -optimal and -optimal,1(G) =(G) =(G) =(G) =2d, and the graph G−NG[a]is connected for every vertex a∈V (G). As an example, Corollary 5 can be applied to Petersen graph P, since it has girth 5 and consists of two cycles of length 5 plus a matching between them. Namely, P=C5∪fC5where fis a perfect matching between the vertices of C5=(01234)and itself defined as f(0)=0, and f(j)=f(j −1)+3(mod 5). Hence, 1====4 holds for Petersen graph, and it is still connected after deleting any vertex of the graph and its three neighbors. This latter fact was proved not only for Petersen graph but for every (3,g)-cage by some of the authors in [16]. This section ends up by recalling that results for matched sum graphs G=G1∪fG2can be read for permutation graphs (as it was done in Corollary 1), by simply taking G1=G2=Hand writing G=Hf. For instance, consider the hypercube Qn=K2×Qn−1, with Q1=K2. Clearly, the n-regular graph Qncan be written as Qn=Qn−1∪idQn−1=Qid n−1with id :V(Q n−1)→V(Q n−1)being the identity permutation. Taking into account that (Qn)=2n−2 and the well-known fact (Qn−1)=(Qn−1)=n−1, we deduce that: (a) (Qn)=(Qn)=2n−2 for every n⩾3, following Theorem 2.3, because (Qn−1)⩾(Qn−1)=n−1. (b) 1(Qn)=(Qn)=(Qn)=2n−2 for every n⩾3 as a consequence of Theorem 2.5, a result previously obtained by Xu et al. in [19]. (c) When n⩾4, Qnsatisfies the conditions of Corollary 4, hence Qnis still connected when any vertex and all its neighbors are deleted from Qn, a property that is also satisfied when n=2,3. 3. Proofs In all the proofs we call cross-edges the edges in G=G1∪fG2joining vertices of G1with vertices of G2, and M denotes the set of cross-edges. Thus G=G1M+G2. For a vertex vin G1we will use the notation vto denote its neighbor in G2, that is vv=vf (v) ∈M.
1990 C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 Proof of Theorem 2.1. (i) Follows directly from the definition of a matched sum graph. (ii) First, for each i=1,2, let uv ∈E(Gi)be such that |Gi(uv)|=(Gi). Then, (G)⩽|G(uv)|=(Gi)+2. Next, let uv ∈E(G) be an edge such that |G(uv)|=(G). On the one hand, if uv ∈E(Gi)for i=1or2, then (G) =|G(uv)|=|Gi(uv)|+2⩾(Gi)+2. On the other hand, if uv ∈M,u∈V(G 1),v∈V(G 2), then (G) =|G(uv)|=dG1(u) +dG2(v)⩾(G1)+(G2). (iii) Let W⊂E(G) be a minimum edge-cut of Gsuch that |W|=(G); that is, G−Wconsists of exactly two connected components, H,H∗(due to the minimality of W). If W=M, then (G) =|W|=|M|=|V(G i)|⩾(Gi)+1 (i =1,2), hence the result follows. Then, we must suppose that W= M,H= Giand H∗= Gi, for both i=1,2. Let us write W=W1∪WM∪W2, with W1⊆E(G1),WM⊆M,W2⊆E(G2). First, when both V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅for i=1,2, we have that W1=∅and W2=∅are edge-cuts for G1and G2, respectively, hence (G) =|W|⩾|W1|+|W2|⩾(G1)+(G2), and the result holds. Second, suppose that one of H,H∗lies entirely in Gi, say V(H)V(G 1). In this case, W2=∅and |V(H)|= |WM|. Moreover, W1is an edge-cut of G1, hence (G1)⩽|W1|.If|W1|⩾(G1)+1 then (G) =|W|=|W1|+ |WM|⩾(G1)+1 and we are done. Hence suppose |W1|⩽(G1)and let us denote |V(H)|=r. Then r(r−1)⩾2|E(H)|= u∈V(H)dG1(u) −|W1|⩾(G1)(r −1), hence either |V(H)|=r=1or|V(H)|=r⩾(G1). In the former case, (G)=|W|=|W1|+|WM|⩾(G1)+1; and in the latter case, (G)=|W|=|W1|+|WM|⩾(G1)+(G1)⩾1+(G1). Then, the proof of (iii) is over. (iv) Let us prove the claimed lower bound for (G). To this end, let F⊂V (G) be any cut set in Gsuch that |F|=(G), and let F1=F∩V(G 1)and F2=F∩V(G 2). If both G1−F1and G2−F2are not connected, then |F|=|F1|+|F2|⩾(G1)+(G2), and the result holds. So, suppose without loss of generality that G2−F2is connected. As G−Fis not connected, there must exist u∈V(G 1−F1)not connected in G−Fwith G2−F2. But then, if vv∈Mis the corresponding cross-edge for each v∈X=NG1−F1[u]we deduce that v∈F2. This implies that |F1|+|F2|⩾|NG1−F1(u) ∩F1|+|X|=dG1(u) +1,and, therefore, (G) =|F|=|F1|+|F2|⩾dG1(u) +1⩾(G1)+1⩾(G), hence the proof is complete. Proof of Theorem 2.2. Set |V(G i)|=,i=1,2. Notice that |V (G)|=|V(G 1)|+|V(G 2)|=2⩾8. Moreover, as Gis not a star, Gis -connected and (G)⩽(G) [9]. Let W⊂E(G) be a minimum restricted edge-cut of Gsuch that |W|=(G); that is, G−Wconsists of exactly two connected components, H,H∗(due to the minimality of W), and have no isolated vertex, |V(H)|⩾2 and |V(H∗)|⩾2. Observe that if W=M, then the result is true since (G) =|M|=. Thus we assume that W= M, hence H= Giand H∗= Gi, for both i=1,2. Let us write W=W1∪WM∪W2, with W1⊆E(G1),WM⊆M,W2⊆E(G2). Notice that if Hsimply consists of two adjacent vertices u∈V(G 1),u∈V(G 2), then (G) =|W|=|G(uu)|⩾(G) and we are done. The same remark holds for H∗. So, we continue the proof by assuming that neither Hnor H∗consists of two vertices joined by an edge in M. For each i=1,2, let us see that Wi=∅implies that Wiis a restricted edge-cut of Gi. Without loss of generality suppose that a∈V(H∗)∩V(G 1)is an isolated vertex in G1−W1, and let aa∈M(so, vertex a∈V(H∗)and aa/∈WM, because Wis a restricted edge-cut of G). Hence |V(H∗)|⩾3. Consider the set of edges W=(W −G1(a)) ∪{aa}⊂E(G). Then G− Wconsists of exactly two components, namely the subgraphs H∗−aand the one induced by V(H)∪{a}. Therefore, Wis another restricted edge-cut of Ghaving cardinality | W|=|W|−dG1(a) +1<|W|=(G) because dG1(a)⩾2, an absurdity. Hence, G1−W1has no isolated vertex. Since Wiis an edge-cut of Gidue to the minimality of W, then Wiis a restricted edge-cut and, therefore, |Wi|⩾(Gi)provided that Wi=∅, for each i=1,2. When both V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅for i=1,2, we have W1=∅and W2=∅, hence |W|⩾|W1|+|W2|⩾(G1)+(G2), and the result holds. To end the proof, suppose without loss of generality that V(H)V(G 1). In this case, W2=∅and 2⩽|V(H)|=|WM|. Firstly, suppose that there exists some v∈V(H) such that |G1(v) ∩W1|⩽1, then |V(H)|⩾|{v}∪(NG1(v) ∩ V(H))|⩾(G1).AsW1is a restricted edge-cut for G1because W1=∅,wehave(G)=|W|=|W1|+|WM|⩾(G1)+
C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 1991 |V(H)|⩾(G1)+(G1). Secondly, assume that |G1(v) ∩W1|⩾2 for all v∈V(H). Let us consider an edge xy ∈E(H) such that |NG1(x) ∩V(H)|⩾|NG1(y) ∩V(H)|. Therefore we can write: |W1|⩾|G1(x) ∩W1|+|G1(y) ∩W1|+ z∈(NG1(x)−y)∩V(H) |G1(z) ∩W1| ⩾|G1(x) ∩W1|+|G1(y) ∩W1|+2|(NG1(x) −y) ∩V(H)| ⩾|G1(x) ∩W1|+|(NG1(x) −y) ∩V(H)|+|G1(y) ∩W1|+|(NG1(y) −x) ∩V(H)| ⩾dG1(x) −1+dG1(y) −1⩾(G1). This fact implies that (G) =|W|=|W1|+|WM|⩾(G1)+2⩾(G), by Theorem 2.1, hence the proof is over. Proof of Corollary 3. Observe that (G1)+(G2)⩾(G1)+(G2)⩾2∗, and also that (Gi)+(Gi)⩾2∗for i=1,2. Therefore, from Theorem 2.2 and taking into account the hypothesis |V(G 1)|=|V(G 2)|⩾2∗⩾4, it suffices to prove that 2∗=(G) in order to complete the proof, since 2∗=2(G) −2. To this end, let us show that there exist two adjacent vertices in Gboth having degree ∗+1=(G). For item (i), the condition (Gi)=2∗−2 implies that there exists some xy ∈E(Gi)such that dGi(x) =dGi(y) =∗, hence dG(x) =dG(y) =∗+1. For item (ii), dG(x) =dG(f (x)) =∗+1 holds by hypothesis, xf (x) being an edge of G. Proof of Theorem 2.3. As |V(G 1)|=|V(G 2)|⩾4, observe that G1,G2and Gare -connected and (G1)⩽(G1), (G2)⩽(G2),(G)⩽(G), taking into account [9].Fori=1,2, notice also that Gitriangle-free implies that every edge uv ∈E(Gi)satisfies |NGi(uv)|=|Gi(uv)|⩾(Gi), hence |V(G i)|⩾(Gi)+2⩾(G), the last inequality being due to Theorem 2.1. We follow the same terminology and kind of reasoning as in the proof of Theorem 2.2. To be more precise, let W=W1∪WM∪W2⊂E(G) be a minimum restricted edge-cut of Gsuch that |W|=(G), W1⊆E(G1),WM⊆M,W2⊆E(G2). Let Hand H∗be the two connected components of G−W, none of which can have isolated vertices. As shown in that proof, (G)⩾|V(G i)|(hence (G)⩾(G)) follows if we assume W=M, and (G)⩾(G) holds if we assume that H(or H∗) consists of two vertices joined by an edge in M. So, the proof continues with H= Giand H∗= Gifor both i=1,2, because W= Mmust be assumed. Again as in the proof of Theorem 2.2, Wi=∅implies that Wiis a restricted edge-cut of Gi, for each i=1,2. Suppose that some of H,H∗lies entirely in Gi, say V(H)V(G 1). In this case, W1=∅,W2=∅and 2⩽|V(H)|= |WM|. Let uv be an edge in H. Taking into account that G1is triangle-free, we have (G) =|W|=|W1|+|WM|⩾|G1(uv) −E(H)|+(|G1(uv) ∩E(H)|+2) =|G1(uv)|+2⩾(G1)+2⩾(G), and we are done. When both V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅for i=1 and 2, we have W1=∅and W2=∅, hence (G) =|W|⩾|W1|+|W2|⩾(G1)+(G2)⩾(G), and the result also holds. Proof of Proposition 2.4. Let xy be an edge in Gsuch that |NG({x,y})|=|G(xy)|=(G). Let us first see that V (G) = NG[{x,y}]. Indeed, if every vertex in NG({x,y})had all its neighbors in NG[{x,y}], then some cycle of length 3 or 4 would appear because (G)⩾2; thus, V (G) = NG[{x,y}] holds under hypothesis (i) or (ii). Furthermore, the claimed inequality is also clear for assertion (iii), since |V (G) −NG[{x,y}]|⩾((G) +3)−((G) +2)=1. Finally, for proving (iv), assume without loss of generality that x∈V(G 1).Ify∈V(G 1), then any cross-edge uu with u∈NG1(x) −ysatisfies that u/∈NG[{x,y}], because clearly u= xand u= y.Ify∈V(G 2), then xy ∈M, NG(x) −y=NG1(x) and NG(y) −x=NG2(y). Hence any u∈NG1(x) has a neighbor u∗/∈NG[{x,y}], because (G)⩾3 and Gis triangle-free. Since we have proved V (G) = NG[{x,y}], then NG({x,y})is a cut. Let us show that (G)⩽(G) by proving that NG({x,y})is a restricted cut, that is, NG(b)NG({x,y})for every vertex b∈V (G). This fact is clear if b∈NG[{x,y}], or under hypothesis (i), because otherwise a cycle of length 4 or 5 appears. It is also clear under hypothesis (iii). For the rest of the items we reason by contradiction assuming that NG(b) ⊆NG({x,y})for some vertex b∈V (G). For (ii), (G)⩾3 implies that vertex bmust be adjacent to two vertices in NG(x) −yor adjacent to two vertices in NG(y) −x, yielding a cycle of length 4 < g(G) since g(G)⩾5, an absurdity. Finally, two cases must be considered under hypothesis (iv). Without loss of generality assume b∈V(G 1). Notice that x,y /∈V(G 1), because b/∈{x,y}.
1992 C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 Hence suppose first x∈V(G 1),y∈V(G 2). Then vertex bmust share dG1(b)⩾2 neighbors with xand one neighbor with y, say b∈V(G 2), and hence there exists a cycle of length 5 going through xy, which contradicts (iv). Second, suppose that both x,y ∈V(G 2), and let x,y∈V(G 1)be such that xx∈Mand yy∈Mare the corresponding cross-edges. Let bb∈Mbe a cross-edge. Then b∈V(G 2)because we are assuming b∈V(G 1)and bmust be adjacent in G1to both x,y, because (G1)⩾(G) −1⩾2. Therefore, xyybxxis a cycle of length 5, against the hypothesis (iv). The proof ends by recalling that every restricted cut is also a P1-cut, so 1(G) exists and 1(G)⩽(G)⩽ (G). Proof of Theorem 2.5. 1(G)⩽(G)⩽(G) follows from Proposition 2.4. Consider any F⊂V (G) such that G−F is not connected and satisfying both the conditions |F|=1(G) and G−Fhas no isolated vertex. Let F1=F∩V(G 1) and F2=F∩V(G 2). If both G1−F1and G2−F2are not connected, then 1(G) =|F|=|F1|+|F2|⩾(G1)+(G2), and the result holds. Thus, assume for instance that G2−F2is connected. Observe that G−Fnot connected implies that there must exist some connected component Hof G1−F1such that u∈F2for every cross-edge uu∈Mwith u∈V(H),so |V(H)|⩽|F2|. Now we can take some uv ∈E(H) because no isolated vertex exists in G−F.AsG1is triangle-free we have |NG1({u, v})|=dG1(u) +dG1(v) −2⩾(G1). Noticing that NG1[{u, v}]⊆F1∪V(H), we can write: 1(G) =|F|=|F1|+|F2|⩾|F1|+|V(H)|⩾|NG1({u, v})|+2⩾(G1)+2⩾(G), ending the proof. Proof of Corollary 4. Let us prove first that NG(b)NG[a]for every pair of vertices a,b ∈V (G) such that b/∈NG[a]. Assuming that a∈V(G 1), let a∈V(G 2)be such that aa∈Mis the corresponding cross-edge. Therefore, NG(b)NG[a]for every vertex b∈V(G 1)∩V(G−NG[a]), because bb∈Mis a cross-edge such that b= a. Moreover, if b∈V(G 2)∩V(G−NG[a]), it follows NG(b)NG[a]since (G2)⩾3 and |V(G 2)∩NG[a]|=1. The same conclusion is obtained when a∈V(G 2)is assumed. Next, let a∈V (G) be any vertex such that dG(a)⩽(G) −2 (observe that (G) −2⩾2(G) −4⩾(G), because (G) =min{(G1)+1,(G2)+1}⩾4). Suppose that G−NG[a]is not connected, and we arrive at a contradiction. Indeed, G−NG[a]disconnected means that NG[a]is a P1-cut, that is, 1(G)⩽|NG[a]| = dG(a) +1⩽(G) −1, contradicting that 1(G) =(G) =(G) as Theorem 2.5 states because (G)⩽(G1)+(G2)by hypothesis. Proof of Corollary 5. Observe that both G1and G2are triangle-free because g(G)⩾5, and also that (G) =2d since Gis (d +1)-regular. From Theorem 2.3, it follows the -optimality of Gin both cases (i) and (ii), since (G1)+(G2)⩾(G1)+(G2)=2d=(G). Let us continue the proof of (ii). Taking into account that (G1)+ (G2)=2d=(G), the chain 1(G)=(G)=(G)=2dis directly obtained from Theorem 2.5; moreover, when d⩾3, each vertex a∈V (G) satisfies dG(a)=(G)=d+1⩽2d−2=(G)−2, hence G−NG[a]is connected by Corollary 4. To complete the proof of (ii), let us assume d=2 and let us take any vertex a∈V (G). Set NG(a) ={x1,x 2,x 3}. If G−NG[a]was not connected, then G−NG[a]would consist of exactly two components, H1,H2(because Gis 3-regular), and each vertex xiwould be adjacent to one vertex yi∈V(H 1)and also to one vertex zi∈V(H 2). As all three vertices y1,y 2,y 3∈V(H 1)must be pairwise different (otherwise, a cycle of length 4 appears), the set of edges {x1y1,x 2y2,x 3y3}is a restricted edge-cut of G, that is, (G)⩽3. This contradicts the fact the (G) =(G) =2d=4, thus G−NG[a]must be connected. Acknowledgments We would like to thank the referees for their helpful suggestions and comments. References [1] C. Balbuena, A. Carmona, J. Fàbrega, M.A. Fiol, Extraconnectivity of graphs with large minimum degree and girth, Discrete Math. 167/168 (1997) 85–100. [2] C. Balbuena, M. Cera, A. Diánez, X. Marcote, P. García-Vázquez, On the restricted connectivity and superconnectivity in graphs with given girth, Discrete Math. 307 (2007) 659–667.
C. Balbuena et al. / Discrete Mathematics 308 (2008) 1985–1993 1993 [3] 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. [4] C. Balbuena, X. Marcote, P. García-Vázquez, On restricted connectivities of permutation graphs, Networks 45 (3) (2005) 113–118. [5] F.T. Boesch, Synthesis of reliable networks—a survey, IEEE Trans. Reliab. 35 (1986) 240–246. [6] F.T. Boesch, R. Tindell, Circulants and their connectivities, J. Graph Theory 8 (4) (1984) 487–499. [7] G. Chartrand, F. Harary, Planar permutation graphs, Ann. Inst. H. Poincaré, Sec. B 3 (1967) 433–438. [8] G. Chartrand, L. Lesniak, Graphs and Digraphs, third ed., Chapman & Hall, London, UK, 1996. [9] A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inf. Process. Lett. 27 (1988) 195–199. [10] J. Fàbrega, M.A. Fiol, On the extraconnectivity of graphs, Discrete Math. 155 (1996) 49–57. [11] M.A. Fiol, J. Fàbrega, M. Escudero, Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31. [12] J.P. Georges, D.W. Mauro, On generalized Petersen graphs labeled with a condition at distance two, Discrete Math. 259 (2002) 311–318. [13] W. Goddard, M.E. Raines, P.J. Slater, Distance and connectivity measures in permutation graphs, Discrete Math. 271 (2003) 61–70. [14] F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. [15] H.-J. Lai, Large survivable nets and the generalized prisms, Discrete Appl. Math. 61 (1995) 181–185. [16] X. Marcote, I. Pelayo, C. Balbuena, Every cubic cage is quasi 4-connected, Discrete Math. 266 (2003) 311–320. [17] B. Piazza, Edge-connectivity of permutation graphs, Congr. Numer. 65 (1988) 7–16. [18] B.L. Piazza, R.D. Ringeisen, Connectivity of generalized prisms over G, Discrete Appl. Math. 30 (1991) 229–233. [19] J.M. Xu, Q. Zhu, X.M. Hou, T. Zhou, On restricted connectivity and extra connectivity of hypercubes and folded hypercubes, J. Shanghai Jiaotong Univ. (Science) 10 (2) (2005) 203–207.