Connectivity measures in matched sum graphs

Connec i i y measu es in ma ched sum g aphs夡 C. Balbuenaa, P. Ga cía-Vázquezb, X. Ma co ea aDepa amen de Ma emà ica Aplicada III, Uni e si a Poli ècnica de Ca alunya, Campus No d, Edifici C2, C/ Jo di Gi ona1i3, E-08034 Ba celona, Spain bDepa amen o de Ma emá ica Aplicada I, Uni e sidad de Se illa, A da Reina Me cedes 2, E-41012 Se illa, Spain Abs ac A ma ched sum g aph G o wo g aphs G1 and G2 o he same o de is ob ained om he union o G1 and G2 and om joining each e ex o G1 wi h one e ex o G2 acco ding o one bijec ion be ween he e ices in V(G1) and V(G2). When G1 =G2 =H hen is jus a pe mu a ion o V(H) and he co esponding ma ched sum g aph is a pe mu a ion g aph H . In his pape , we de i e lowe bounds o he connec i i y, edge-connec i i y, and di e en condi ional connec i i ies in ma ched sum g aphs, and p esen su ficien condi ions which gua an ee maximum alues o hese condi ional connec i i ies. . Keywo ds: Res ic ed edge-cu ; Res ic ed cu ; Connec i i y; Condi ional connec i i y; Supe connec i i y; Res ic ed connec i i y 1. In oduc ion Le G=(V, E) be a simple g aph wi h e ex se V=V (G) and edge se E=E(G). Th oughou his pape , only undi ec ed simple g aphs wi hou loops o mul iple edges ha ing a leas wo e ices a e conside ed. Fo e e y S⊂V, he neighbo hood o S deno ed by N(S)=NG(S) is he se o e ices in V−S ha a e adjacen o some e ex in S, and le NG[S]=NG(S) ∪S. The deg ee o a e ex is d( ) =dG( ) =|N( )|, and =(G) is he minimum deg ee o e all e ices o G. Fo e e y u∈V, he edge-neighbo hood o u is (u) =G(u) ={e∈ E:eis inciden wi h u}. Fo e e y u ∈E, he edge-bounda y o u deno ed by (u ) =G(u ) is he se o edges (u ) =((u) ∪( )) −u , and |(u )|=d(u) +d( ) −2 is called he edge-deg ee o u . The minimum edge- deg ee o Gis deno ed by =(G) =min{|(u )|:u ∈E}.Acu [edge-cu ] o a connec ed g aph Gis a se So e ices [edges] such ha G−Sis no connec ed. The connec i i y =(G) [edge-connec i i y,=(G)]is he minimum ca dinali y o a cu [edge-cu ], and i is widely known ha (G)⩽(G)⩽(G). A connec ed g aph Gis called maximally connec ed [maximally edge-connec ed]i (G) =(G) [(G) =(G)].Unless o he wise s a ed, we ollow [8] o addi ional e minology and defini ions. 夡Resea ch suppo ed by he Minis y o Educa ion and Science, Spain, and he Eu opean Regional De elopmen Fund (ERDF) unde p ojec MTM2005-08990-C02-02. E-mail add esses: [email p o ec ed] (C. Balbuena), [email p o ec ed] (P. Ga cía-Vázquez), ancisco.ja ie [email p o ec ed] (X. Ma co e). doi:10.1016/j.disc.2007.04.051 1986 C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 Two connec ed g aphs wi h he same connec i i y [edge-connec i i y] may be conside ed o ha e di e en eliabil- i ies, mainly due o he p ope ies sa isfied by ei he minimum cu s [edge-cu s] o he associa ed componen s. In his ega d, Es ahanian and Hakimi [9] in oduced wo indices o connec i i y by conside ing cu s o edge-cu s ha sa is y some condi ion. Mo e p ecisely, a cu [edge-cu ] Xis called es ic ed i no e ex uo he g aph is such ha N(u) ⊆X [(u) ⊆X]; he es ic ed connec i i y =(G) and he es ic ed edge-connec i i y =(G) a e hen defined as =min{|X|:X⊂Vis a es ic ed cu }, =min{|X|:X⊂Eis a es ic ed edge-cu }. A ew yea s la e , Balbuena e al. [1] app oached he eliabili y o a g aph Gby conside ing cu s [edge-cu s] Xsuch ha e e y componen o G−Xhas a leas wo e ices. These P1-cu s [edge P1-cu s] we e in oduced ollowing [10], in he con ex o he condi ional connec i i ies o mula ed in [14]. Obse e ha a cu [edge-cu ] XisaP1-cu [edge P1-cu ] i no e ex u∈V−Xo he g aph is such ha N(u) ⊆X[no e ex u∈Vsa isfies (u) ⊆X]. The co esponding indices o connec i i y 1=1(G) and 1=1(G) we e defined as 1=min{|X|:X⊂VisaP1-cu }, 1=min{|X|:X⊂Eis an edge P1-cu }. The supe connec i i y and edge-supe connec i i y p oposed in [5,6] can be measu ed by 1(G) and 1(G), espec i ely. A g aph is supe connec ed i e e y minimum cu consis s o he e ices adjacen o one e ex ha does no belong o he cu ; see Boesch [5], Boesch and Tindell [6], and Fiol e al. [11]. I is easy o see ha a supe connec ed g aph Gis necessa ily maximally connec ed (bu he con e se is no ue, as happens, o ins ance, o C6), and also ha 1(G) > (G) is a necessa y and su ficien condi ion o G o be supe connec ed, p o ided ha 1(G) can be defined. In a simila way, he concep o an edge-supe connec ed g aph can be in oduced. The e a e ob ious simila i ies be ween he pai s o indices (G),(G) and 1(G),1(G). Indeed, 1(G)=(G),bu 1(G)⩽(G), because any es ic ed cu is a P1-cu (howe e , he con e se is no ue, as shown in [9]). These indices a e well defined whene e some specific ype o cu o edge-cu exis s. In his espec , i was shown [9] ha (G) exis s i Gis no a s a and i s o de is a leas 4, and (G)⩽(G). The si ua ion o e ices seems much mo e complica ed. Nei he (G) no 1(G) exis s o a numbe o g aphs G. E en hough o ou knowledge no cha ac e iza ion o g aphs o which ei he (G) o 1(G) exis s has been gi en, one can assu e he exis ence o hese indices o some amilies o g aphs. Fo ins ance, i is easy o see ha bo h (G) and 1(G) exis o all hose g aphs o gi h g⩾5 and minimum deg ee ⩾3, o hose o gi h g⩾6 (obse e ha N({u, })is a es ic ed cu o e e y edge u ), all o hese sa is ying 1(G)⩽(G)⩽(G). A g aph Gis -connec ed [-connec ed]i (G) [(G)]exis s, and is said o be -op imal [-op imal]i (G) =(G) [(G) =(G)]. Some su ficien condi ions o a g aph o be -op imal and -op imal ha e been gi en in e ms o he gi h [2,3]. In his pape , we a e in e es ed in p o iding lowe bounds on he connec i i ies ,,1, o ma ched sum g aphs. Ma ched sum g aphs we e in oduced by Geo ges and Mau o [12] as ollows. Gi en wo g aphs G1,G2o he same o de |V(G 1)|=|V(G 2)|, and a ma ching M om V(G 1) o V(G 2), he ma ched sum g aph o G1and G2, deno ed by G1M+G2, is he g aph wi h V(G 1M+G2)=V(G 1)∪V(G 2)and E(G1M+G2)=E(G1)∪E(G2)∪M. Since he ma ching Mcan be w i en by means o a bijec ion :V(G 1)→V(G 2)as M={x (x) :x∈V(G 1)}, i may be use ul o deno e al e na ely a ma ched sum g aph G1M+G2by G1∪ G2. Ma ched sum g aphs cons i u e a gene aliza ion o pe mu a ion g aphs, which we e in oduced by Cha and and Ha a y in [7]. Indeed, when G1=G2=H, any bijec ion :V(H)→V(H)is a pe mu a ion o V(H), and he co esponding ma ched sum g aph H∪ His he pe mu a ion g aph H . Examples o pe mu a ion g aphs include hype cubes, p isms and some gene alized Pe e sen g aphs. See [4,13,15,17,18] o esul s and p ope ies on pe mu a ion g aphs. This pape is de o ed o s udy how connec ed ma ched sum g aphs a e. Fo he conside ed ma ched sum g aphs G1∪ G2, i mus be emphasized ha G1and G2need no be isomo phic, con a ily o he case o pe mu a ion g aphs. In Sec ion 2, we p esen ou esul s and we p o ide he de ails o he p oo s in Sec ion 3. 2. Main esul s Le G1and G2be wo g aphs such ha |V(G 1)|=|V(G 2)|, and any bijec ion om V(G 1) o V(G 2). Clea ly, G1 and G2connec ed yield a connec ed ma ched sum g aph G=G1∪ G2. C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 1987 e1 e2 e3 Fig. 1. The se {e1,e 2,e 3}is a minimum es ic ed edge-cu . Theo em 2.1. Le G1and G2be wo connec ed g aphs o he same o de |V(G 1)|=|V(G 2)|and minimum deg ees (G1)⩾2, (G2)⩾2. Then o any bijec ion om V(G 1) o V(G 2), he ollowing asse ions hold o he ma ched sum g aph G=G1∪ G2: (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). (i ) min{(G1)+(G2), (G)}⩽(G)⩽(G). As an immedia e consequence o Theo em 2.1 we ob ain he ollowing esul s conce ning he connec i i y and edge-connec i i y o pe mu a ion g aphs which we e al eady p o ed by Lai in [15]. Recall ha he pe mu a ion g aph Hcan be w i en as H∪H, whe e :V(H)→V(H)is a pe mu a ion. Co olla y 1 (Lai [15]).Fo all g aphs H and pe mu a ions : min{2(H ), (H) +1}⩽(H )⩽(H) +1, min{2(H ), (H) +1}⩽(H )⩽(H) +1. Nex , we s udy he es ic ed edge-connec i i y o ma ched sum g aphs G=G1∪ G2when G1and G2a e bo h connec ed and ha e minimum deg ees (G1)⩾2, (G2)⩾2, espec i ely. Fo he simples case, |V(G 1)|=|V(G 2)|=3, each Gimus be a iangle, and i is easily seen ha all possible ma ched sum g aphs G=G1∪ G2a e isomo phic, and hey a e no -op imal since (G) =3<4=(G) (see Fig. 1, whe e {e1,e 2,e 3}is he ma ching co esponding o a bijec ion :V(G 1)→V(G 2)). Thus, we assume |V(G 1)|=|V(G 2)|⩾4. Theo em 2.2. Le G1and G2be wo connec ed g aphs o he same o de |V(G 1)|=|V(G 2)|⩾4, and minimum deg ees (G1)⩾2, (G2)⩾2. Then o any bijec ion om V(G 1) o V(G 2), he g aph G=G1∪ G2is -connec ed and min{(G1)+(G2), (G1)+(G1), (G2)+(G2), |V (G)|/2,(G)}⩽(G)⩽(G). Le G1and G2be wo g aphs o minimum deg ees (G1)⩾(G2)⩾2 such ha |V(G 1)|=|V(G 2)|⩾min{(G1)+ 2,(G2)+2}. Then om Theo em 2.1, i ollows ha |V(G 1)|=|V(G 2)|⩾(G)⩾4. I we assume (Gi)⩾(Gi)− (Gi)+2 o bo h i=1,2, hen (G1)+(G2)⩾((G1)−(G1)−(G2)+2)+(G2)+2⩾((G1)−(G2)) + (G2)+2⩾(G), whe e he inequali y (G1)⩾2(G1)−2 has been aken in o accoun . Hence he nex co olla y ollows as a consequence o Theo em 2.2. Co olla y 2. Le G1and G2be wo connec ed g aphs o minimum deg ees (G1)⩾2, (G2)⩾2, he same o de |V(G 1)|=|V(G 2)|⩾min{(G1)+2,(G2)+2},and sa is ying (Gi)⩾(Gi)−(Gi)+2 o bo h i=1,2. Then, o any bijec ion om V(G 1) o V(G 2), he g aph G=G1∪ G2is -op imal. Obse e ha bo h g aphs G1and G2ha e been assumed o be maximally edge-connec ed in he abo e esul , since (Gi)⩾(Gi)−(Gi)+2⩾(Gi)implies easily ha (Gi)=(Gi). The ollowing co olla y shows ha -op imali y o a ma ched sum g aph G1∪ G2can be gua an eed e en i one o G1,G2is no maximally edge-connec ed. Co olla y 3. Le G1and G2be wo connec ed g aphs o minimum deg ees (G1),(G2)and he same o de |V(G 1)|= |V(G 2)|⩾2∗,whe e ∗=min{(G1), (G2)}⩾2. Assume ha (Gi)⩾∗ o bo h i=1,2. Le be any bijec ion om V(G 1) o V(G 2),and le G=G1∪ G2.Then,Gis-op imal and (G) =(G) =2(G) −2i any o he ollowing 1988 C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 G1 G2 Fig. 2. E e y ma ched sum g aph G=G1∪ G2is -op imal (edges o he ma ching a e no depic ed). condi ions holds: (i) (Gi)=2∗−2 o i=1o i=2. (ii) (G1)=(G2)=∗,and is such ha dG2( (x)) =dG1(x) =∗ o some e ex x∈V(G 1). An applica ion o poin (i) o Co olla y 3 may be seen in Fig. 2. G aph G1is no maximally edge-connec ed, because (G1)=3<4=(G1); g aph G2(Pe e sen g aph) sa isfies (G2)=3=(G2).As∗=min{(G1), (G2)}=3 and (G2)=4=2∗−2, i u ns ou ha o e e y bijec ion om V(G 1) o V(G 2), he ma ched sum g aph G=G1∪ G2 sa isfies (G) =(G) =2(G) −2=6, hence Gis -op imal. F om now on, we a e going o app oach he es ic ed connec i i ies (G),(G) and he supe connec i i y 1(G) o iangle- ee ma ched sum g aphs G. Hence we only deal wi h g aphs o which |G(u )|=|NG({u, })|holds o e e y edge u . Thus, we can w i e (G) =min{|NG({u, })|:u ∈E(G)}. Theo em 2.3. Le G1and G2be wo iangle- ee connec ed g aphs o he same o de and minimum deg ees (G1)⩾2, (G2)⩾2. Then o any bijec ion om V(G 1) o V(G 2), he g aph G=G1∪ G2is -connec ed and min{(G1)+ (G2), (G)}⩽(G)⩽(G). Obse e ha his esul is an imp o emen o Theo em 2.2 o iangle- ee g aphs, a leas o hose cases whe e (G1)>(G2)( hus(G2)+(G2)<(G1)+(G2))o (G2)>(G1)( ha is,(G1)+(G1)<(G1)+(G2)). No ice also ha he -op imali y o he ma ched sum g aph G=G1∪ G2is di ec ly gua an eed by Theo em 2.3 whene e (G1)+(G2)⩾(G). Nex , le us ocus ou a en ion on he ( e ex-) connec i i y pa ame e s 1(G),(G). As poin ed ou in he in o- duc ion, o some g aphs Gone can assu e bo h he exis ence o hese wo indices and he chain 1(G)⩽(G)⩽(G), bu a comple e cha ac e iza ion o g aphs o which hese wo s a emen s hold has no been gi en ye . The ollowing p oposi ion gi es ou su ficien condi ions in his ega d o iangle- ee g aphs. P oposi ion 2.4. Le G be a connec ed iangle- ee g aph o minimum deg ee (G)⩾2. Then,Gis-connec ed and 1(G)⩽(G)⩽(G) i a leas one o he ollowing asse ions holds: (i) The gi h is g(G)⩾6. C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 1989 (ii) (G)⩾3and he gi h is g(G)⩾5. (iii) |V (G)|⩾(G)+3,and he e exis s an edge xy such ha bo h |G(xy)|=(G) and |NG({x,y})∩NG(z)|⩽dG(z)−1 o any e ex z/∈{x,y}. (i ) Gis a ma ched sum g aph,G=G1∪ G2,(G)⩾3, and no edge o he ma ching M={x (x) :x∈V(G 1)} belongs o a cycle o leng h fi e. The ollowing heo em may be seen as an imp o emen o i em (i ) o Theo em 2.1. Indeed, we show ha a ma ched sum g aph Go wo iangle- ee g aphs Gi,i=1,2, migh ha e 1(G) > (G)⩾(G1)+(G2), wi hou any kind o equi emen on 1(Gi),i=1,2. Theo em 2.5. Le G1and G2be wo connec ed iangle- ee g aphs o he same o de and minimum deg ees (G1)⩾2, (G2)⩾2. Then o any bijec ion om V(G 1) o V(G 2), he g aph G=G1∪ G2is -connec ed and min{(G1)+ (G2), (G)}⩽1(G)⩽(G)⩽(G) i G sa isfies any o he condi ions (i), (ii), (iii) o (i ) in P oposi ion 2.4. Clea ly, 1(G) =(G) =(G) holds o e e y ma ched sum g aph G=G1∪ G2sa is ying bo h he equi emen s in Theo em 2.5 and he cons ain (G1)+(G2)⩾(G). Recall ha NG[S]=NG(S) ∪S o e e y subse So e ices. Co olla y 4. Le G1and G2be wo connec ed iangle- ee g aphs o he same o de and minimum deg ees (G1)⩾3, (G2)⩾3. Le be a bijec ion om V(G 1) o V(G 2),and le G=G1∪ G2.Then, o e e y e ex a∈V (G) such ha dG(a)⩽(G) −2, he g aph G−NG[a]is connec ed i (G1)+(G2)⩾(G) and G sa isfies any o he condi ions (i), (ii), (iii) o (i ) in P oposi ion 2.4. Co olla y 5. Le G1and G2be wo connec ed d- egula g aphs,d⩾2, o he same o de . Le be a bijec ion om V(G 1) o V(G 2),le G=G1∪ G2,and suppose ha he gi h is g(G)⩾5. The ollowing s a emen s hold: (i) I (Gi)=d o bo h i=1,2, hen G is -op imal and (G) =(G) =2d. (ii) I (Gi)=d o bo h i=1,2, hen G is bo h -op imal and -op imal,1(G) =(G) =(G) =(G) =2d, and he g aph G−NG[a]is connec ed o e e y e ex a∈V (G). As an example, Co olla y 5 can be applied o Pe e sen g aph P, since i has gi h 5 and consis s o wo cycles o leng h 5 plus a ma ching be ween hem. Namely, P=C5∪ C5whe e is a pe ec ma ching be ween he e ices o C5=(01234)and i sel defined as (0)=0, and (j)= (j −1)+3(mod 5). Hence, 1====4 holds o Pe e sen g aph, and i is s ill connec ed a e dele ing any e ex o he g aph and i s h ee neighbo s. This la e ac was p o ed no only o Pe e sen g aph bu o e e y (3,g)-cage by some o he au ho s in [16]. This sec ion ends up by ecalling ha esul s o ma ched sum g aphs G=G1∪ G2can be ead o pe mu a ion g aphs (as i was done in Co olla y 1), by simply aking G1=G2=Hand w i ing G=H . Fo ins ance, conside he hype cube Qn=K2×Qn−1, wi h Q1=K2. Clea ly, he n- egula g aph Qncan be w i en as Qn=Qn−1∪idQn−1=Qid n−1wi h id :V(Q n−1)→V(Q n−1)being he iden i y pe mu a ion. Taking in o accoun ha (Qn)=2n−2 and he well-known ac (Qn−1)=(Qn−1)=n−1, we deduce ha : (a) (Qn)=(Qn)=2n−2 o e e y n⩾3, ollowing Theo em 2.3, because (Qn−1)⩾(Qn−1)=n−1. (b) 1(Qn)=(Qn)=(Qn)=2n−2 o e e y n⩾3 as a consequence o Theo em 2.5, a esul p e iously ob ained by Xu e al. in [19]. (c) When n⩾4, Qnsa isfies he condi ions o Co olla y 4, hence Qnis s ill connec ed when any e ex and all i s neighbo s a e dele ed om Qn, a p ope y ha is also sa isfied when n=2,3. 3. P oo s In all he p oo s we call c oss-edges he edges in G=G1∪ G2joining e ices o G1wi h e ices o G2, and M deno es he se o c oss-edges. Thus G=G1M+G2. Fo a e ex in G1we will use he no a ion  o deno e i s neighbo in G2, ha is = ( ) ∈M. 1990 C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 P oo o Theo em 2.1. (i) Follows di ec ly om he defini ion o a ma ched sum g aph. (ii) Fi s , o each i=1,2, le u ∈E(Gi)be such ha |Gi(u )|=(Gi). Then, (G)⩽|G(u )|=(Gi)+2. Nex , le u ∈E(G) be an edge such ha |G(u )|=(G). On he one hand, i u ∈E(Gi) o i=1o 2, hen (G) =|G(u )|=|Gi(u )|+2⩾(Gi)+2. On he o he hand, i u ∈M,u∈V(G 1), ∈V(G 2), hen (G) =|G(u )|=dG1(u) +dG2( )⩾(G1)+(G2). (iii) Le W⊂E(G) be a minimum edge-cu o Gsuch ha |W|=(G); ha is, G−Wconsis s o exac ly wo connec ed componen s, H,H∗(due o he minimali y o W). I W=M, hen (G) =|W|=|M|=|V(G i)|⩾(Gi)+1 (i =1,2), hence he esul ollows. Then, we mus suppose ha W= M,H= Giand H∗= Gi, o bo h i=1,2. Le us w i e W=W1∪WM∪W2, wi h W1⊆E(G1),WM⊆M,W2⊆E(G2). Fi s , when bo h V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅ o i=1,2, we ha e ha W1=∅and W2=∅a e edge-cu s o G1and G2, espec i ely, hence (G) =|W|⩾|W1|+|W2|⩾(G1)+(G2), and he esul holds. Second, suppose ha one o H,H∗lies en i ely in Gi, say V(H)V(G 1). In his case, W2=∅and |V(H)|= |WM|. Mo eo e , W1is an edge-cu o G1, hence (G1)⩽|W1|.I |W1|⩾(G1)+1 hen (G) =|W|=|W1|+ |WM|⩾(G1)+1 and we a e done. Hence suppose |W1|⩽(G1)and le us deno e |V(H)|= . Then ( −1)⩾2|E(H)|= u∈V(H)dG1(u) −|W1|⩾(G1)( −1), hence ei he |V(H)|= =1o |V(H)|= ⩾(G1). In he o me case, (G)=|W|=|W1|+|WM|⩾(G1)+1; and in he la e case, (G)=|W|=|W1|+|WM|⩾(G1)+(G1)⩾1+(G1). Then, he p oo o (iii) is o e . (i ) Le us p o e he claimed lowe bound o (G). To his end, le F⊂V (G) be any cu se in Gsuch ha |F|=(G), and le F1=F∩V(G 1)and F2=F∩V(G 2). I bo h G1−F1and G2−F2a e no connec ed, hen |F|=|F1|+|F2|⩾(G1)+(G2), and he esul holds. So, suppose wi hou loss o gene ali y ha G2−F2is connec ed. As G−Fis no connec ed, he e mus exis u∈V(G 1−F1)no connec ed in G−Fwi h G2−F2. Bu hen, i ∈Mis he co esponding c oss-edge o each ∈X=NG1−F1[u]we deduce ha ∈F2. This implies ha |F1|+|F2|⩾|NG1−F1(u) ∩F1|+|X|=dG1(u) +1,and, he e o e, (G) =|F|=|F1|+|F2|⩾dG1(u) +1⩾(G1)+1⩾(G), hence he p oo is comple e.  P oo o Theo em 2.2. Se |V(G i)|=,i=1,2. No ice ha |V (G)|=|V(G 1)|+|V(G 2)|=2⩾8. Mo eo e , as Gis no a s a , Gis -connec ed and (G)⩽(G) [9]. Le W⊂E(G) be a minimum es ic ed edge-cu o Gsuch ha |W|=(G); ha is, G−Wconsis s o exac ly wo connec ed componen s, H,H∗(due o he minimali y o W), and ha e no isola ed e ex, |V(H)|⩾2 and |V(H∗)|⩾2. Obse e ha i W=M, hen he esul is ue since (G) =|M|=. Thus we assume ha W= M, hence H= Giand H∗= Gi, o bo h i=1,2. Le us w i e W=W1∪WM∪W2, wi h W1⊆E(G1),WM⊆M,W2⊆E(G2). No ice ha i Hsimply consis s o wo adjacen e ices u∈V(G 1),u∈V(G 2), hen (G) =|W|=|G(uu)|⩾(G) and we a e done. The same ema k holds o H∗. So, we con inue he p oo by assuming ha nei he Hno H∗consis s o wo e ices joined by an edge in M. Fo each i=1,2, le us see ha Wi=∅implies ha Wiis a es ic ed edge-cu o Gi. Wi hou loss o gene ali y suppose ha a∈V(H∗)∩V(G 1)is an isola ed e ex in G1−W1, and le aa∈M(so, e ex a∈V(H∗)and aa/∈WM, because Wis a es ic ed edge-cu o G). Hence |V(H∗)|⩾3. Conside he se o edges  W=(W −G1(a)) ∪{aa}⊂E(G). Then G− Wconsis s o exac ly wo componen s, namely he subg aphs H∗−aand he one induced by V(H)∪{a}. The e o e,  Wis ano he es ic ed edge-cu o Gha ing ca dinali y | W|=|W|−dG1(a) +1<|W|=(G) because dG1(a)⩾2, an absu di y. Hence, G1−W1has no isola ed e ex. Since Wiis an edge-cu o Gidue o he minimali y o W, hen Wiis a es ic ed edge-cu and, he e o e, |Wi|⩾(Gi)p o ided ha Wi=∅, o each i=1,2. When bo h V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅ o i=1,2, we ha e W1=∅and W2=∅, hence |W|⩾|W1|+|W2|⩾(G1)+(G2), and he esul holds. To end he p oo , suppose wi hou loss o gene ali y ha V(H)V(G 1). In his case, W2=∅and 2⩽|V(H)|=|WM|. Fi s ly, suppose ha he e exis s some ∈V(H) such ha |G1( ) ∩W1|⩽1, hen |V(H)|⩾|{ }∪(NG1( ) ∩ V(H))|⩾(G1).AsW1is a es ic ed edge-cu o G1because W1=∅,weha e(G)=|W|=|W1|+|WM|⩾(G1)+ C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 1991 |V(H)|⩾(G1)+(G1). Secondly, assume ha |G1( ) ∩W1|⩾2 o all ∈V(H). Le us conside an edge xy ∈E(H) such ha |NG1(x) ∩V(H)|⩾|NG1(y) ∩V(H)|. The e o e we can w i e: |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 ac implies ha (G) =|W|=|W1|+|WM|⩾(G1)+2⩾(G), by Theo em 2.1, hence he p oo is o e .  P oo o Co olla y 3. Obse e ha (G1)+(G2)⩾(G1)+(G2)⩾2∗, and also ha (Gi)+(Gi)⩾2∗ o i=1,2. The e o e, om Theo em 2.2 and aking in o accoun he hypo hesis |V(G 1)|=|V(G 2)|⩾2∗⩾4, i su fices o p o e ha 2∗=(G) in o de o comple e he p oo , since 2∗=2(G) −2. To his end, le us show ha he e exis wo adjacen e ices in Gbo h ha ing deg ee ∗+1=(G). Fo i em (i), he condi ion (Gi)=2∗−2 implies ha he e exis s some xy ∈E(Gi)such ha dGi(x) =dGi(y) =∗, hence dG(x) =dG(y) =∗+1. Fo i em (ii), dG(x) =dG( (x)) =∗+1 holds by hypo hesis, x (x) being an edge o G. P oo o Theo em 2.3. As |V(G 1)|=|V(G 2)|⩾4, obse e ha G1,G2and Ga e -connec ed and (G1)⩽(G1), (G2)⩽(G2),(G)⩽(G), aking in o accoun [9].Fo i=1,2, no ice also ha Gi iangle- ee implies ha e e y edge u ∈E(Gi)sa isfies |NGi(u )|=|Gi(u )|⩾(Gi), hence |V(G i)|⩾(Gi)+2⩾(G), he las inequali y being due o Theo em 2.1. We ollow he same e minology and kind o easoning as in he p oo o Theo em 2.2. To be mo e p ecise, le W=W1∪WM∪W2⊂E(G) be a minimum es ic ed edge-cu o Gsuch ha |W|=(G), W1⊆E(G1),WM⊆M,W2⊆E(G2). Le Hand H∗be he wo connec ed componen s o G−W, none o which can ha e isola ed e ices. As shown in ha p oo , (G)⩾|V(G i)|(hence (G)⩾(G)) ollows i we assume W=M, and (G)⩾(G) holds i we assume ha H(o H∗) consis s o wo e ices joined by an edge in M. So, he p oo con inues wi h H= Giand H∗= Gi o bo h i=1,2, because W= Mmus be assumed. Again as in he p oo o Theo em 2.2, Wi=∅implies ha Wiis a es ic ed edge-cu o Gi, o each i=1,2. Suppose ha some o H,H∗lies en i ely in Gi, say V(H)V(G 1). In his case, W1=∅,W2=∅and 2⩽|V(H)|= |WM|. Le u be an edge in H. Taking in o accoun ha G1is iangle- ee, we ha e (G) =|W|=|W1|+|WM|⩾|G1(u ) −E(H)|+(|G1(u ) ∩E(H)|+2) =|G1(u )|+2⩾(G1)+2⩾(G), and we a e done. When bo h V(H)∩V(G i)=∅and V(H∗)∩V(G i)=∅ o i=1 and 2, we ha e W1=∅and W2=∅, hence (G) =|W|⩾|W1|+|W2|⩾(G1)+(G2)⩾(G), and he esul also holds.  P oo o P oposi ion 2.4. Le xy be an edge in Gsuch ha |NG({x,y})|=|G(xy)|=(G). Le us fi s see ha V (G) = NG[{x,y}]. Indeed, i e e y e ex in NG({x,y})had all i s neighbo s in NG[{x,y}], hen some cycle o leng h 3 o 4 would appea because (G)⩾2; hus, V (G) = NG[{x,y}] holds unde hypo hesis (i) o (ii). Fu he mo e, he claimed inequali y is also clea o asse ion (iii), since |V (G) −NG[{x,y}]|⩾((G) +3)−((G) +2)=1. Finally, o p o ing (i ), assume wi hou loss o gene ali y ha x∈V(G 1).I y∈V(G 1), hen any c oss-edge uu wi h u∈NG1(x) −ysa isfies ha u/∈NG[{x,y}], because clea ly u= xand u= y.I y∈V(G 2), hen xy ∈M, NG(x) −y=NG1(x) and NG(y) −x=NG2(y). Hence any u∈NG1(x) has a neighbo u∗/∈NG[{x,y}], because (G)⩾3 and Gis iangle- ee. Since we ha e p o ed V (G) = NG[{x,y}], hen NG({x,y})is a cu . Le us show ha (G)⩽(G) by p o ing ha NG({x,y})is a es ic ed cu , ha is, NG(b)NG({x,y}) o e e y e ex b∈V (G). This ac is clea i b∈NG[{x,y}], o unde hypo hesis (i), because o he wise a cycle o leng h 4 o 5 appea s. I is also clea unde hypo hesis (iii). Fo he es o he i ems we eason by con adic ion assuming ha NG(b) ⊆NG({x,y}) o some e ex b∈V (G). Fo (ii), (G)⩾3 implies ha e ex bmus be adjacen o wo e ices in NG(x) −yo adjacen o wo e ices in NG(y) −x, yielding a cycle o leng h 4 < g(G) since g(G)⩾5, an absu di y. Finally, wo cases mus be conside ed unde hypo hesis (i ). Wi hou loss o gene ali y assume b∈V(G 1). No ice ha x,y /∈V(G 1), because b/∈{x,y}. 1992 C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 Hence suppose fi s x∈V(G 1),y∈V(G 2). Then e ex bmus sha e dG1(b)⩾2 neighbo s wi h xand one neighbo wi h y, say b∈V(G 2), and hence he e exis s a cycle o leng h 5 going h ough xy, which con adic s (i ). Second, suppose ha bo h x,y ∈V(G 2), and le x,y∈V(G 1)be such ha xx∈Mand yy∈Ma e he co esponding c oss-edges. Le bb∈Mbe a c oss-edge. Then b∈V(G 2)because we a e assuming b∈V(G 1)and bmus be adjacen in G1 o bo h x,y, because (G1)⩾(G) −1⩾2. The e o e, xyybxxis a cycle o leng h 5, agains he hypo hesis (i ). The p oo ends by ecalling ha e e y es ic ed cu is also a P1-cu , so 1(G) exis s and 1(G)⩽(G)⩽ (G). P oo o Theo em 2.5. 1(G)⩽(G)⩽(G) ollows om P oposi ion 2.4. Conside any F⊂V (G) such ha G−F is no connec ed and sa is ying bo h he condi ions |F|=1(G) and G−Fhas no isola ed e ex. Le F1=F∩V(G 1) and F2=F∩V(G 2). I bo h G1−F1and G2−F2a e no connec ed, hen 1(G) =|F|=|F1|+|F2|⩾(G1)+(G2), and he esul holds. Thus, assume o ins ance ha G2−F2is connec ed. Obse e ha G−Fno connec ed implies ha he e mus exis some connec ed componen Ho G1−F1such ha u∈F2 o e e y c oss-edge uu∈Mwi h u∈V(H),so |V(H)|⩽|F2|. Now we can ake some u ∈E(H) because no isola ed e ex exis s in G−F.AsG1is iangle- ee we ha e |NG1({u, })|=dG1(u) +dG1( ) −2⩾(G1). No icing ha NG1[{u, }]⊆F1∪V(H), we can w i e: 1(G) =|F|=|F1|+|F2|⩾|F1|+|V(H)|⩾|NG1({u, })|+2⩾(G1)+2⩾(G), ending he p oo .  P oo o Co olla y 4. Le us p o e fi s ha NG(b)NG[a] o e e y pai o e ices a,b ∈V (G) such ha b/∈NG[a]. Assuming ha a∈V(G 1), le a∈V(G 2)be such ha aa∈Mis he co esponding c oss-edge. The e o e, NG(b)NG[a] o e e y e ex b∈V(G 1)∩V(G−NG[a]), because bb∈Mis a c oss-edge such ha b= a. Mo eo e , i b∈V(G 2)∩V(G−NG[a]), i ollows NG(b)NG[a]since (G2)⩾3 and |V(G 2)∩NG[a]|=1. The same conclusion is ob ained when a∈V(G 2)is assumed. Nex , le a∈V (G) be any e ex such ha dG(a)⩽(G) −2 (obse e ha (G) −2⩾2(G) −4⩾(G), because (G) =min{(G1)+1,(G2)+1}⩾4). Suppose ha G−NG[a]is no connec ed, and we a i e a a con adic ion. Indeed, G−NG[a]disconnec ed means ha NG[a]is a P1-cu , ha is, 1(G)⩽|NG[a]| = dG(a) +1⩽(G) −1, con adic ing ha 1(G) =(G) =(G) as Theo em 2.5 s a es because (G)⩽(G1)+(G2)by hypo hesis.  P oo o Co olla y 5. Obse e ha bo h G1and G2a e iangle- ee because g(G)⩾5, and also ha (G) =2d since Gis (d +1)- egula . F om Theo em 2.3, i ollows he -op imali y o Gin bo h cases (i) and (ii), since (G1)+(G2)⩾(G1)+(G2)=2d=(G). Le us con inue he p oo o (ii). Taking in o accoun ha (G1)+ (G2)=2d=(G), he chain 1(G)=(G)=(G)=2dis di ec ly ob ained om Theo em 2.5; mo eo e , when d⩾3, each e ex a∈V (G) sa isfies dG(a)=(G)=d+1⩽2d−2=(G)−2, hence G−NG[a]is connec ed by Co olla y 4. To comple e he p oo o (ii), le us assume d=2 and le us ake any e ex a∈V (G). Se NG(a) ={x1,x 2,x 3}. I G−NG[a]was no connec ed, hen G−NG[a]would consis o exac ly wo componen s, H1,H2(because Gis 3- egula ), and each e ex xiwould be adjacen o one e ex yi∈V(H 1)and also o one e ex zi∈V(H 2). As all h ee e ices y1,y 2,y 3∈V(H 1)mus be pai wise di e en (o he wise, a cycle o leng h 4 appea s), he se o edges {x1y1,x 2y2,x 3y3}is a es ic ed edge-cu o G, ha is, (G)⩽3. This con adic s he ac he (G) =(G) =2d=4, hus G−NG[a]mus be connec ed.  Acknowledgmen s We would like o hank he e e ees o hei help ul sugges ions and commen s. Re e ences [1] C. Balbuena, A. Ca mona, J. Fàb ega, M.A. Fiol, Ex aconnec i i y o g aphs wi h la ge minimum deg ee and gi h, Disc e e Ma h. 167/168 (1997) 85–100. [2] C. Balbuena, M. Ce a, A. Diánez, X. Ma co e, P. Ga cía-Vázquez, On he es ic ed connec i i y and supe connec i i y in g aphs wi h gi en gi h, Disc e e Ma h. 307 (2007) 659–667. C. Balbuena e al. / Disc e e Ma hema ics 308 (2008) 1985–1993 1993 [3] C. Balbuena, P. Ga cía-Vázquez, X. Ma co e, Su ficien condi ions o -op imali y in g aphs wi h gi h g, J. G aph Theo y 52 (2006) 73–86. [4] C. Balbuena, X. Ma co e, P. Ga cía-Vázquez, On es ic ed connec i i ies o pe mu a ion g aphs, Ne wo ks 45 (3) (2005) 113–118. [5] F.T. Boesch, Syn hesis o eliable ne wo ks—a su ey, IEEE T ans. Reliab. 35 (1986) 240–246. [6] F.T. Boesch, R. Tindell, Ci culan s and hei connec i i ies, J. G aph Theo y 8 (4) (1984) 487–499. [7] G. Cha and, F. Ha a y, Plana pe mu a ion g aphs, Ann. Ins . H. Poinca é, Sec. B 3 (1967) 433–438. [8] G. Cha and, L. Lesniak, G aphs and Dig aphs, hi d ed., Chapman & Hall, London, UK, 1996. [9] A.H. Es ahanian, S.L. Hakimi, On compu ing a condi ional edge-connec i i y o a g aph, In . P ocess. Le . 27 (1988) 195–199. [10] J. Fàb ega, M.A. Fiol, On he ex aconnec i i y o g aphs, Disc e e Ma h. 155 (1996) 49–57. [11] M.A. Fiol, J. Fàb ega, M. Escude o, Sho pa hs and connec i i y in g aphs and dig aphs, A s Combin. 29B (1990) 17–31. [12] J.P. Geo ges, D.W. Mau o, On gene alized Pe e sen g aphs labeled wi h a condi ion a dis ance wo, Disc e e Ma h. 259 (2002) 311–318. [13] W. Godda d, M.E. Raines, P.J. Sla e , Dis ance and connec i i y measu es in pe mu a ion g aphs, Disc e e Ma h. 271 (2003) 61–70. [14] F. Ha a y, Condi ional connec i i y, Ne wo ks 13 (1983) 347–357. [15] H.-J. Lai, La ge su i able ne s and he gene alized p isms, Disc e e Appl. Ma h. 61 (1995) 181–185. [16] X. Ma co e, I. Pelayo, C. Balbuena, E e y cubic cage is quasi 4-connec ed, Disc e e Ma h. 266 (2003) 311–320. [17] B. Piazza, Edge-connec i i y o pe mu a ion g aphs, Cong . Nume . 65 (1988) 7–16. [18] B.L. Piazza, R.D. Ringeisen, Connec i i y o gene alized p isms o e G, Disc e e Appl. Ma h. 30 (1991) 229–233. [19] J.M. Xu, Q. Zhu, X.M. Hou, T. Zhou, On es ic ed connec i i y and ex a connec i i y o hype cubes and olded hype cubes, J. Shanghai Jiao ong Uni . (Science) 10 (2) (2005) 203–207.