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.