On the vulnerability of some families of graphs

On he ulne abili y o some amilies o g aphs Roc´ıo M. Casablanca, Ana R. Di´anez and Ped o Ga c´ıa-V´azquez Uni e sidad de Se illa Se illa Abs ac The oughness o a noncomple e g aph Gis defined as τ(G)= min{|S|/ω(G−S)}, whe e he minimum is aken o e all cu - se s So e ices o Gand ω(G−S) deno es he numbe o componen s o he esul an g aph G−Sby dele ion o S.In his pape , we in es iga e he oughness o he co ona o wo connec ed g aphs and ob ain he exac alue o he co ona o wo g aphs belonging o some amilies as pa hs, cycles, wheels o comple e g aphs. We also ge an uppe and a lowe bounds o he oughness o he ca esian p oduc o he comple e g aph K2wi h a p ede e mined g aph G. 1 In oduc ion Th oughou his pape , all he g aphs a e simple, ha is, wi hou loops and mul iple edges. No a ions and e minology no explici ly gi en he e can be ound in he book by Cha and and Lesniak [3]. Le Gbe a g aph wi h e ex se V(G)andedgese E(G). The g aph Gis called connec ed i e e y pai o e ices is joined by a pa h. A cu se in a g aph Gis a subse S⊂V(G) o e ices o Gsuch ha G−Sis no connec ed. The exis ence o a cu se is always gua an eed in e e y g aph diffe en om a comple e g aph Kn. The index o connec i i y o G, deno ed by κ(G), is defined as he minimum ca dinali y o e all cu se s o G,i Gis a noncomple e g aph, o |V(G)|−1, o he wise. The e a e se e al measu es o ulne abili y o a ne wo k. The ulne - abili y pa ame e s one gene ally encoun e s a e he indices o connec i i y 183 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. and edge-connec i i y. These wo pa ame e s gi e he minimum cos o dis up he ne wo k, bu hey ake no accoun o wha emains a e he des uc ion. To measu e he ulne abili y o ne wo ks mo e p ope ly, some ulne abili y pa ame e s ha e been in oduced and s udied. Among hem a e oughness, in eg i y, sca e ing numbe , enaci y and se e al a ian s o connec i i y and edge-connec i i y called condi ional connec i i y, each o which measu es no only he difficul y o b eaking down he ne wo k bu also he damage caused. In gene al, o mos o he a o emen ioned pa am- e e s, he co esponding compu a ional p oblem is NP-ha d. So i is o in e es o gi e he o mulae o algo i hms o compu ing hese pa ame e s o special classes o g aphs. Fo ou pu pose, we deal wi h he no ion o oughness, in oduced by Ch ´a al [4], which pays special a en ion o he ela ionship be ween he ca dinali y o he up u e se in he ne wo k and he numbe o componen s a e he up u e. The pa ame e is defined as τ(G)=min{|S|/ω(G−S):S⊆J(G)}, whe e J(G)={S⊂V(G):Sis a cu se o Go G−Sis an isola ed e ex}, and ω(G−S) deno es he numbe o componen s in he esul an g aph G−Sby emo ing S. Since his pa ame e was in oduced, lo s o esea ch has been done, mainly ela ing oughness condi ions o he exis ence o cycle s uc u es. His o ically, mos o he esea ch was based on a numbe o conjec u es in [4]. Some o mos in e es ing esul s a e [1, 2, 5]. Howe e , exac alues o τ(G) a e known only o a ew amilies o g aphs as pa hs and cycles [4], he ca esian p oduc o wo comple e g aphs [4] and o pa hs and/o cycles [7], and he composi ion o wo g aphs, one o hem being a pa h, a cycle o a comple e bipa i e g aph [7]. In his pape we ocus on he oughness o wo amilies o g aphs: he co ona G◦Ho wo g aphs [6] and he ca esian p oduc K2×G. I o each e ex xin a g aph G, we in oduce a new e ex xand join xand xby an edge, he esul ing g aph is called he co ona o G.The ope a ion o adding one e ex o each e ex o Gand connec ing hem by an edge can be gene alized as ollows. The co ona o any wo g aphs G and H, deno ed by G◦H, is he g aph ob ained by aking one copy o G and |V(G)|copies o H, and hen joining he i h e ex o G o e e y e ex 184 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. in he i h copy o H. Obse e ha he pa icula case in which H=K1, he g aph G◦K1is called he co ona o G.Theca esian p oduc K2×G o he comple e g aph K2and any g aph Gis he g aph wi h e ex se V(K2)×V(G)inwhich e ex(i, u), o i=1,2, is adjacen o e ex (j, ) whene e i=jand u ∈E(G), o i=jand u= [6]. The e exis s se e al kinds o in e connec ion ne wo ks whose s uc u e can be modeled in e ms o he ca esian p oduc o he co ona o wo p ede e mined ne wo ks. The ca esian p oduc o g aphs seeks o es ablish pa allel connec ions be ween iden ical s uc u es, minimizing he cos o such connec ions. The co ona o wo p ede e mined g aphs is o en p esen in elec ic ne wo ks dis ibu ed in a big ci y whe e each ans o me mus gua an ee he ene gy supply o i s ca chmen a ea. In o de o op imize esou ces, he dis ibu ion o ans o me s is made by di iding he ci y in ca chmen a eas o he same en i y. Thus, in e ms o G aph Theo y, he s uc u e o be analyzed consis s o a ne wo k ans o me s, modeled by a g aph, Gwhe e each ans o me is connec ed wi h i s ca chmen a ea, modeled by he g aph H. The esul an g aph is he co ona G◦Ho Gand H. In he main enance o elec ic ne wo ks is ele an o a oid he dis up ion o he ene gy supply, bu when he ailu e in some nodes p oduces he up u e o he ne wo k, he g ea e he numbe o agmen s in which he ne wo k has been di ided, he g ea e he cos o econs uc ion. The ela ionship be ween he ca dinali y o a cu se o a g aph Gand he emaining componen a e dis up ion is analyzed by he no ion o oughness, defined abo e. So ou aim in his wo k is o de e mine he oughness o he co ona G◦Ho wo connec ed g aphs Gand Hin e ms o known pa ame e s o hem. As a consequence, we will deduce he exac alue o he co ona o some amilies o g aphs in ol ing s a s, pa hs, cycles, wheels o comple e g aphs. We will also find an uppe and a lowe bounds o he oughness o K2×G, o any a bi a y g aph G. 2 The oughness o he co ona o wo g aphs 2.1 No a ions and ema ks Le G,Hbe wo connec ed g aphs on mand n e ices, espec i ely. Le us se V(G)={ 1,..., m}and deno e by Hi he copy o H ha is joined o e ex io Gin G◦H. Thus, e e y cu se So G◦Hwill hence o h exp essed as S=S0∪m i=1 Si,whe eS0⊆V(G)andSi⊆V(Hi), o 185 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. i=1,...,m.Wedeno ebyω0=ω(G−S0), ωi=ω(Hi−Si), i=1,...,m, ha is, he numbe o componen o G−S0and Hi−Si,i=1,...,m, espec i ely. Acu se o G◦Hsuch ha |S|/ω(G◦H−S)=τ(G◦H) will be called aτ-cu o G◦H. Le us see some ema ks on he τ-cu o he co ona o wo g aphs. Rema k 1 I S=S0∪m i=1 Siis a cu se o he co ona G◦Ho wo connec ed g aphs G,H, henS0=∅. P oo : I S0=∅ hen e e y e ex o G◦H−Sei he is in V(G)o is adjacen o one e ex o G, hence, G◦H−Sis connec ed, agains he ac ha Sis a cu se o G◦H. Rema k 2 Le S=S0∪m i=1 Sibe a τ-cu o he co ona G◦Ho wo connec ed g aphs G,H.I j∈S0 hen ei he Sj=∅o Sjis a cu se o Hj. P oo : Le j∈S0and suppose by way o con adic ion ha Sj=∅is no acu se o Hj. Le us conside he se S∗=S Sj. Obse e ha ei he Hj−Sjis a componen o G◦H−So Sj=V(Hj)andHjis a componen o G◦H−S∗.Thus,ω(G◦H−S∗)≥ω(G◦H−S) and he e o e, |S∗| ω(G◦H−S∗)≤|S|−n ω(G◦H−S)<|S| ω(G◦H−S)=τ(G◦H−S), which con adic s he hypo hesis ha Sis a τ-cu o G◦H. Then ei he Sj=∅o Sjis a cu se o Hj. Rema k 3 Le S=S0∪m i=1 Sibe a τ-cu o he co ona G◦Ho wo connec ed g aphs G,H.I j∈ S0 hen Sj=∅. P oo : Le j∈ S0and suppose by way o con adic ion ha Sj=∅.Le us conside he se S∗=S Sj. Obse e ha ei he Hj−Sjbelongs o he componen o G◦H−S ha con ains e ex jo Sj=V(Hj)and Hjbelongs o he componen o G◦H−S∗ ha con ains e ex j.Thus, ω(G◦H−S∗)=ω(G◦H−S) and he e o e, |S∗| ω(G◦H−S∗)=|S|−n ω(G◦H−S)<|S| ω(G◦H−S)=τ(G◦H−S), 186 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. which is again a con adic ion wi h he ac ha Sis a τ-cu o G◦H. Then Sj=∅. Le S=S0∪m i=1 Sibe a τ-cu o G◦H. F om now on, we may assume wi hou loss o gene ali y ha he e ices o he se V(G)={ 1,..., m} a e o de ed so ha |S1|≥···≥|Sm|.Le k∈{1,...,m}be he maximum in ege such ha Si=∅ o all i=1,...,k. Then, as an immedia e consequence o Rema k 1, Rema k 2 and Rema k 3, i ollows ha |S|= |S0|+ k  i=1 |Si|and ω(G◦H−S)=ω0+ k  i=1 ωi+|S0|−k. 2.2 Main esul s Le G,Hbe wo connec ed g aphs on mand n e ices, espec i ely. Ou pu pose is o de e mine he oughness o he co ona G◦Ho Gand H.To begin wi h, gi en a τ-cu o G◦H, he fi s ques ion ha we mus answe is we he e e y copy o g aph Hcan be disconnec ed o be disconnec ed in he same way. The ollowing lemma p o ides an answe o his ques ion. Lemma 4 Le G,Hbe wo connec ed g aphs o o de mand n, espec- i ely, and le S=S0∪m i=1 Sibe a τ-cu o G◦Ho minimum ca dinali y. I Si=∅,Sj=∅, o i, j =1,...,m wi h i=j, hen|Si|=|Sj|and ωi=ωj. P oo : Le us conside he e ex se V(G)={ 1,..., m}o de ed so ha |S1|≥···≥|Sm|,andle k∈{1,...,m}be he maximum in ege such ha Si=∅ o all i=1,...,k.Thus,|S|=|S0|+k i=1 |Si|.SinceSis a τ-cu o G◦H,weha e τ(G◦H)= |S0|+ k  i=1 |Si| ω0+ k  i=1 ωi+|S0|−k≤|S0|+k|S| ω0+kω+|S0|−k, o e e y =1,...,k, (1) 187 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. yielding o -|S0|+ k  i=1 |Si|.kω+(ω0+|S0|−k) k  i=1 |Si| ≤|S0| k  i=1 ωi+-ω0+ k  i=1 ωi+|S0|−k.k|S|, o =1,...,k. (2) By aking summa ion in (2) we deduce ha -|S0|+ k  i=1 |Si|.k k  =1 ω+k(ω0+|S0|−k) k  i=1 |Si| ≤k|S0| k  i=1 ωi+-ω0+ k  i=1 ωi+|S0|−k.k k  =1 |S| =-|S0|+ k  =1 |S|.k k  i=1 ωi+k(ω0+|S0|−k) k  =1 |S|, which implies ha all he inequali ies o (2) become equali ies, and he e- o e, all he inequali ies o (1) become equali ies. Thus, τ(G◦H)= |S0|+k|Si| ω0+kωi+|S0|−k=|S0|+k|Sj| ω0+kωj+|S0|−k, o all i, j =1,...,k, (3) which means ha he se S∗=S0∪k i=1 S∗ i,whe eS∗ i=Sk, o all i=1,...,k,isalsoaτ-cu . Hence, |S|=|S0|+ k  i=1 |Si|≥|S0|+k|Sk|=|S∗|, yielding o |S1|=···=|Sk|because Shas minimum ca dinali y. Mo eo e , gi en any wo subse s Si,Sj,wi hi, j ∈{1,...,k}and i=j, om (3) i is clea ha ωi=ωj. Then he esul holds.  Gi en a τ-cu S=S0∪m i=1 Sio G◦Hwi h minimum ca dinali y, by Lemma 4 we may assume wi hou loss o gene ali y ha o each i= 1,...,m,ei he Si=∅o Si=SH, o someSH⊂V(H). Fu he mo e, i 188 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. ollows ha ei he ω(Hi−Si)=1(i Si=∅)o ω(Hi−Si)=ω(H−SH) (i Si=SH). To uppe bound he index o oughness o G◦H, i is enough o find a cu se So G◦Hand compu e |S|/ω(G◦H−S). The e a e some al e na i es in he choice o such a cu se , as he ollowing p oposi ion shows. P oposi ion 5 Le G,Hbe wo connec ed g aphs o o de mand n, e- spec i ely. Le SH⊂V(H)be any cu se o Ho ca dinali y |SH|=pand deno e by q=ω(H−SH).Then τ(G◦H)≤min 1 2,τ(G) 1+τ(G),1+p 1+q,1+p 1 τ(G)+q%. P oo : Fi s , le jbe any e ex o V(G) and le us conside he se S= { j}in G◦H.ThenSis a cu se and G◦H−Ssince jsepa a es he copy Hjo H om G◦H−({ j}∪V(Hj)). Fu he mo e, G◦H−Shas a leas wo componen s, i.e., ω(G◦H−S)=1+ω(G◦H−({ j}∪V(Hj))) ≥2, yielding o τ(G◦H)≤|S| ω(G◦H−S)≤1 2. Second, le S⊂V(G)beaτ-cu o G.ThenSis a cu se o G◦Hand ω(G◦H−S)=ω(G−S)+|S|and he e o e, τ(G◦H)≤|S| ω(G◦H−S)≤|S| ω(G−S)+|S|= |S| ω(G−S) 1+ |S| ω(G−S) =τ(G) 1+τ(G). Thi d, le SH⊂V(H) be any cu se o Ho ca dinali y |SH|=p and deno e by q=ω(H−SH). Take any e ex j∈V(G)andse Sj=SH⊂V(Hj). Le us conside he e ex se S={ j}∪Sjand obse e ha Sis a cu se o G◦H. Indeed, ω(G◦H−S)=ω(G− j)+ω(Hj−Sj)≥ 1+ω(Hj−Sj). Thus,i wedeno ebyp=|Sj|and deno e by q=ω(H−SH), i ollows ha τ(G◦H)≤|S| ω(G◦H−S)≤1+|Sj| 1+ω(Hj−Sj)=1+p 1+q. Finally, ake any cu se SH⊂V(H)o Ho ca dinali y |SH|=pand deno e by q=ω(H−SH). Le S0={w1,...,w |S0|}⊂V(G)beaτ-cu o Gand deno e by Hi he copy o Hjoined o e ex wiin G◦H, o 189 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. i=1,...,|S0|. Le us conside he e ex se S=S0∪|S0| i=1 Si,whe e Si=SH, o e e y i=1,...,|S0|. Clea ly Sis a cu se o G◦Hand ω(G◦H−S)=ω(G−S0)+|S0|ω(H−SH). Hence, τ(G◦H)≤|S| ω(G◦H−S)=|S0|+|S0||SH| ω(G−S0)+|S0|ω(H−SH) =|S0|(1 + p) ω(G−S0)+|S0|q =τ(G)(1 + p) 1+τ(G)q =1+p 1/τ(G)+q. Thus, τ(G◦H)≤min 1 2,τ(G) 1+τ(G),1+p 1+q,1+p 1 τ(G)+qand he esul holds.  The nex esul gi es a necessa y condi ion o a τ-cu o G◦H o con ain e ices o some copy Hi. Lemma 6 Le G,Hbe wo connec ed g aphs o o de mand n, espec- i ely, and le S=S0∪m i=1 Sibe a τ-cu o G◦Ho minimum ca dinali y. I Sj=∅ o some j=1,...,m, hen|Sj|/ω(Hj−Sj)<1/2. P oo : F om Lemma 4 he e exis s a e ex se SH⊂V(H) such ha ei he Si=∅o Si=SH, o e e y i=1,...,m. So wi hou loss o gene ali y we may assume ha he e is an in ege k∈{1,...,m}such ha S=S0∪k i=1 SH; ha is,Si=SHi i∈{1,...,k}and Si=∅o he wise. The e o e, i is enough o us o p o e ha |SH|/ω(H−SH)<1/2. To cla i y exp essions, deno e by ω0=ω(G−S0)andωH=ω(H−SH). By applying Rema k 1, we know ha S0=∅, and om Rema k 2 and Rema k 3 i ollows ha k≤|S0|.Thus,|S|=|S0|+k|SH|and ω(G◦H−S)= ω0+kωH+|S0|−k. By applying P oposi ion 5 we know ha τ(G◦H)≤1/2, which implies ha |S| ω(G◦H−S)=|S0|+k|SH| ω0+kωH+|S0|−k≤1 2, yielding o |SH| ωH≤1 2+ω0−(|S0|+k) 2kωH .(4) 190 On he ulne abili y o some amilies o g aphs R. M. Casablanca e al. Since S0=∅because o Rema k 1, and k≥1, i S0is no a cu se o G hen ω0≤1 (i.e., ω0=0i S0=V(G), and ω0= 1 o he wise). Hence, applying inequali y ω0−(|S0|+k)<0in(4),weha e|SH| ωH<1 2.Thus, suppose ha S0⊂V(G) is a cu se o G. Fi s assume ha |S0|/ω0≥1. This means ha ω0−(|S0|+k)< ω0−|S0|≤0, yielding in (4) o |SH| ωH<1 2. Second assume ha |S0|/ω0<1. Since S0is a cu se o G hen i is also a cu se o G◦Hand ω(G◦H−S0)=ω0+|S0|. The e o e, by using ha Sis a τ-cu o G◦H, i ollows ha |S0| ω0+|S0|≥τ(G◦H)= |S0|+k|SH| ω0+kωH+|S0|−k>|S0|+k|SH| ω0+kωH+|S0|.(5) Combining he fi s and he las membe s o (5) we deduce ha |SH| ωH <|S0| ω0+|S0|=|S0| ω0 1+|S0| ω0 <1 2, because |S0|/ω0<1. This concludes he p oo .  F om hese p e ious esul s i ollows he nex heo em whe e he ough- ness o he co ona G◦Ho wo connec ed g aphs is de e mined in e ms os some pa ame e o Gand H. Theo em 7 Le G,Hbe wo connec ed g aphs o o de mand n, espec- i ely. Then he ollowing asse ions holds: (i) I τ(G)≥1and τ(H)≥1/2, henτ(G◦H)=1 2. (ii) I τ(G)<1and τ(H)≥1/2, henτ(G◦H)= τ(G) 1+τ(G). (iii) I τ(G)≥1and τ(H)<1/2, hen τ(G◦H)= min SH∈J(H)1+|SH| 1+ω(H−SH). (i ) I τ(G)<1and τ(H)<1/2, hen τ(G◦H)=minτ(G) 1+τ(G),min SH∈J(H) 1+|SH| 1 τ(G)+ω(H−SH)%. 191