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