On the vulnerability of some families of graphs

On the vulnerability of some families of graphs Roc´ıo M. Casablanca, Ana R. Di´anez and Pedro Garc´ıa-V´azquez Universidad de Sevilla Sevilla Abstract The toughness of a noncomplete graph Gis defined as τ(G)= min{|S|/ω(G−S)}, where the minimum is taken over all cutsets Sof vertices of Gand ω(G−S) denotes the number of components of the resultant graph G−Sby deletion of S.In this paper, we investigate the toughness of the corona of two connected graphs and obtain the exact value for the corona of two graphs belonging to some families as paths, cycles, wheels or complete graphs. We also get an upper and a lower bounds for the toughness of the cartesian product of the complete graph K2with a predetermined graph G. 1 Introduction Throughout this paper, all the graphs are simple, that is, without loops and multiple edges. Notations and terminology not explicitly given here can be found in the book by Chartrand and Lesniak [3]. Let Gbe a graph with vertex set V(G)andedgesetE(G). The graph Gis called connected if every pair of vertices is joined by a path. A cutset in a graph Gis a subset S⊂V(G) of vertices of Gsuch that G−Sis not connected. The existence of a cutset is always guaranteed in every graph different from a complete graph Kn. The index of connectivity of G, denoted by κ(G), is defined as the minimum cardinality over all cutsets of G,ifGis a noncomplete graph, or |V(G)|−1, otherwise. There are several measures of vulnerability of a network. The vulnerability parameters one generally encounters are the indices of connectivity 183 On the vulnerability of some families of graphs R. M. Casablanca et al. and edge-connectivity. These two parameters give the minimum cost to disrupt the network, but they take no account of what remains after the destruction. To measure the vulnerability of networks more properly, some vulnerability parameters have been introduced and studied. Among them are toughness, integrity, scattering number, tenacity and several variants of connectivity and edge-connectivity called conditional connectivity, each of which measures not only the difficulty of breaking down the network but also the damage caused. In general, for most of the aforementioned parameters, the corresponding computational problem is NP-hard. So it is of interest to give the formulae or algorithms for computing these parameters for special classes of graphs. For our purpose, we deal with the notion of toughness, introduced by Chv´atal [4], which pays special attention to the relationship between the cardinality of the rupture set in the network and the number of components after the rupture. The parameter is defined as τ(G)=min{|S|/ω(G−S):S⊆J(G)}, where J(G)={S⊂V(G):Sis a cutset of Gor G−Sis an isolated vertex}, and ω(G−S) denotes the number of components in the resultant graph G−Sby removing S. Since this parameter was introduced, lots of research has been done, mainly relating toughness conditions to the existence of cycle structures. Historically, most of the research was based on a number of conjectures in [4]. Some of most interesting results are [1, 2, 5]. However, exact values of τ(G) are known only for a few families of graphs as paths and cycles [4], the cartesian product of two complete graphs [4] and of paths and/or cycles [7], and the composition of two graphs, one of them being a path, a cycle or a complete bipartite graph [7]. In this paper we focus on the toughness of two families of graphs: the corona G◦Hof two graphs [6] and the cartesian product K2×G. If for each vertex xin a graph G, we introduce a new vertex xand join xand xby an edge, the resulting graph is called the corona of G.The operation of adding one vertex for each vertex of Gand connecting them by an edge can be generalized as follows. The corona of any two graphs G and H, denoted by G◦H, is the graph obtained by taking one copy of G and |V(G)|copies of H, and then joining the ith vertex of Gto every vertex 184 On the vulnerability of some families of graphs R. M. Casablanca et al. in the ith copy of H. Observe that the particular case in which H=K1, the graph G◦K1is called the corona of G.Thecartesian product K2×G of the complete graph K2and any graph Gis the graph with vertex set V(K2)×V(G)inwhichvertex(i, u), for i=1,2, is adjacent to vertex (j, v) whenever i=jand uv ∈E(G), or i=jand u=v[6]. There exists several kinds of interconnection networks whose structure can be modeled in terms of the cartesian product or the corona of two predetermined networks. The cartesian product of graphs seeks to establish parallel connections between identical structures, minimizing the cost of such connections. The corona of two predetermined graphs is often present in electric networks distributed in a big city where each transformer must guarantee the energy supply of its catchment area. In order to optimize resources, the distribution of transformers is made by dividing the city in catchment areas of the same entity. Thus, in terms of Graph Theory, the structure to be analyzed consists of a network transformers, modeled by a graph, Gwhere each transformer is connected with its catchment area, modeled by the graph H. The resultant graph is the corona G◦Hof Gand H. In the maintenance of electric networks is relevant to avoid the disruption of the energy supply, but when the failure in some nodes produces the rupture of the network, the greater the number of fragments in which the network has been divided, the greater the cost of reconstruction. The relationship between the cardinality of a cutset of a graph Gand the remaining component after disruption is analyzed by the notion of toughness, defined above. So our aim in this work is to determine the toughness of the corona G◦Hof two connected graphs Gand Hin terms of known parameters of them. As a consequence, we will deduce the exact value of the corona of some families of graphs involving stars, paths, cycles, wheels or complete graphs. We will also find an upper and a lower bounds for the toughness of K2×G, for any arbitrary graph G. 2 The toughness of the corona of two graphs 2.1 Notations and remarks Let G,Hbe two connected graphs on mand nvertices, respectively. Let us set V(G)={v1,...,v m}and denote by Hithe copy of Hthat is joined to vertex viof Gin G◦H. Thus, every cutset Sof G◦Hwill henceforth expressed as S=S0∪m i=1 Si,whereS0⊆V(G)andSi⊆V(Hi), for 185 On the vulnerability of some families of graphs R. M. Casablanca et al. i=1,...,m.Wedenotebyω0=ω(G−S0), ωi=ω(Hi−Si), i=1,...,m, that is, the number of component of G−S0and Hi−Si,i=1,...,m, respectively. AcutsetofG◦Hsuch that |S|/ω(G◦H−S)=τ(G◦H) will be called aτ-cut of G◦H. Let us see some remarks on the τ-cut of the corona of two graphs. Remark 1 If S=S0∪m i=1 Siis a cutset of the corona G◦Hof two connected graphs G,H,thenS0=∅. Proof: If S0=∅then every vertex of G◦H−Seither is in V(G)oris adjacent to one vertex of G, hence, G◦H−Sis connected, against the fact that Sis a cutset of G◦H. Remark 2 Let S=S0∪m i=1 Sibe a τ-cut of the corona G◦Hof two connected graphs G,H.Ifvj∈S0then either Sj=∅or Sjis a cutset of Hj. Proof: Let vj∈S0and suppose by way of contradiction that Sj=∅is not acutsetofHj. Let us consider the set S∗=S\Sj. Observe that either Hj−Sjis a component of G◦H−Sor Sj=V(Hj)andHjis a component of G◦H−S∗.Thus,ω(G◦H−S∗)≥ω(G◦H−S) and therefore, |S∗| ω(G◦H−S∗)≤|S|−n ω(G◦H−S)<|S| ω(G◦H−S)=τ(G◦H−S), which contradicts the hypothesis that Sis a τ-cut of G◦H. Then either Sj=∅or Sjis a cutset of Hj. Remark 3 Let S=S0∪m i=1 Sibe a τ-cut of the corona G◦Hof two connected graphs G,H.Ifvj∈ S0then Sj=∅. Proof: Let vj∈ S0and suppose by way of contradiction that Sj=∅.Let us consider the set S∗=S\Sj. Observe that either Hj−Sjbelongs to the component of G◦H−Sthat contains vertex vjor Sj=V(Hj)and Hjbelongs to the component of G◦H−S∗that contains vertex vj.Thus, ω(G◦H−S∗)=ω(G◦H−S) and therefore, |S∗| ω(G◦H−S∗)=|S|−n ω(G◦H−S)<|S| ω(G◦H−S)=τ(G◦H−S), 186 On the vulnerability of some families of graphs R. M. Casablanca et al. which is again a contradiction with the fact that Sis a τ-cut of G◦H. Then Sj=∅. Let S=S0∪m i=1 Sibe a τ-cut of G◦H. From now on, we may assume without loss of generality that the vertices of the set V(G)={v1,...,v m} are ordered so that |S1|≥···≥|Sm|.Letk∈{1,...,m}be the maximum integer such that Si=∅for all i=1,...,k. Then, as an immediate consequence of Remark 1, Remark 2 and Remark 3, it follows that |S|= |S0|+ k  i=1 |Si|and ω(G◦H−S)=ω0+ k  i=1 ωi+|S0|−k. 2.2 Main results Let G,Hbe two connected graphs on mand nvertices, respectively. Our purpose is to determine the toughness of the corona G◦Hof Gand H.To begin with, given a τ-cut of G◦H, the first question that we must answer is wether every copy of graph Hcan be disconnected to be disconnected in the same way. The following lemma provides an answer to this question. Lemma 4 Let G,Hbe two connected graphs of order mand n, respectively, and let S=S0∪m i=1 Sibe a τ-cut of G◦Hof minimum cardinality. If Si=∅,Sj=∅,fori, j =1,...,m with i=j,then|Si|=|Sj|and ωi=ωj. Proof: Let us consider the vertex set V(G)={v1,...,v m}ordered so that |S1|≥···≥|Sm|,andletk∈{1,...,m}be the maximum integer such that Si=∅for all i=1,...,k.Thus,|S|=|S0|+k i=1 |Si|.SinceSis a τ-cut of G◦H,wehave τ(G◦H)= |S0|+ k  i=1 |Si| ω0+ k  i=1 ωi+|S0|−k≤|S0|+k|S| ω0+kω+|S0|−k, for every =1,...,k, (1) 187 On the vulnerability of some families of graphs R. M. Casablanca et al. yielding to -|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|,for =1,...,k. (2) By taking summation in (2) we deduce that -|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 that all the inequalities of (2) become equalities, and therefore, all the inequalities of (1) become equalities. Thus, τ(G◦H)= |S0|+k|Si| ω0+kωi+|S0|−k=|S0|+k|Sj| ω0+kωj+|S0|−k, for all i, j =1,...,k, (3) which means that the set S∗=S0∪k i=1 S∗ i,whereS∗ i=Sk, for all i=1,...,k,isalsoaτ-cut. Hence, |S|=|S0|+ k  i=1 |Si|≥|S0|+k|Sk|=|S∗|, yielding to |S1|=···=|Sk|because Shas minimum cardinality. Moreover, given any two subsets Si,Sj,withi, j ∈{1,...,k}and i=j, from (3) it is clear that ωi=ωj. Then the result holds.  Given a τ-cut S=S0∪m i=1 Siof G◦Hwith minimum cardinality, by Lemma 4 we may assume without loss of generality that for each i= 1,...,m,eitherSi=∅or Si=SH,forsomeSH⊂V(H). Furthermore, it 188 On the vulnerability of some families of graphs R. M. Casablanca et al. follows that either ω(Hi−Si)=1(ifSi=∅)orω(Hi−Si)=ω(H−SH) (if Si=SH). To upper bound the index of toughness of G◦H, it is enough to find a cutset Sof G◦Hand compute |S|/ω(G◦H−S). There are some alternatives in the choice of such a cutset, as the following proposition shows. Proposition 5 Let G,Hbe two connected graphs of order mand n,respectively. Let SH⊂V(H)be any cutset of Hof cardinality |SH|=pand denote by q=ω(H−SH).Then τ(G◦H)≤min 1 2,τ(G) 1+τ(G),1+p 1+q,1+p 1 τ(G)+q%. Proof: First, let vjbe any vertex of V(G) and let us consider the set S= {vj}in G◦H.ThenSis a cutset and G◦H−Ssince vjseparates the copy Hjof Hfrom G◦H−({vj}∪V(Hj)). Furthermore, G◦H−Shas at least two components, i.e., ω(G◦H−S)=1+ω(G◦H−({vj}∪V(Hj))) ≥2, yielding to τ(G◦H)≤|S| ω(G◦H−S)≤1 2. Second, let S⊂V(G)beaτ-cut of G.ThenSis a cutset of G◦Hand ω(G◦H−S)=ω(G−S)+|S|and therefore, τ(G◦H)≤|S| ω(G◦H−S)≤|S| ω(G−S)+|S|= |S| ω(G−S) 1+ |S| ω(G−S) =τ(G) 1+τ(G). Third, let SH⊂V(H) be any cutset of Hof cardinality |SH|=p and denote by q=ω(H−SH). Take any vertex vj∈V(G)andset Sj=SH⊂V(Hj). Let us consider the vertex set S={vj}∪Sjand observe that Sis a cutset of G◦H. Indeed, ω(G◦H−S)=ω(G−vj)+ω(Hj−Sj)≥ 1+ω(Hj−Sj). Thus,ifwedenotebyp=|Sj|and denote by q=ω(H−SH), it follows that τ(G◦H)≤|S| ω(G◦H−S)≤1+|Sj| 1+ω(Hj−Sj)=1+p 1+q. Finally, take any cutset SH⊂V(H)ofHof cardinality |SH|=pand denote by q=ω(H−SH). Let S0={w1,...,w |S0|}⊂V(G)beaτ-cut of Gand denote by Hithe copy of Hjoined to vertex wiin G◦H,for 189 On the vulnerability of some families of graphs R. M. Casablanca et al. i=1,...,|S0|. Let us consider the vertex set S=S0∪|S0| i=1 Si,where Si=SH, for every i=1,...,|S0|. Clearly Sis a cutset of 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 the result holds.  The next result gives a necessary condition for a τ-cut of G◦Hto contain vertices of some copy Hi. Lemma 6 Let G,Hbe two connected graphs of order mand n, respectively, and let S=S0∪m i=1 Sibe a τ-cut of G◦Hof minimum cardinality. If Sj=∅for some j=1,...,m,then|Sj|/ω(Hj−Sj)<1/2. Proof: From Lemma 4 there exists a vertex set SH⊂V(H) such that either Si=∅or Si=SH, for every i=1,...,m. So without loss of generality we may assume that there is an integer k∈{1,...,m}such that S=S0∪k i=1 SH;thatis,Si=SHif i∈{1,...,k}and Si=∅otherwise. Therefore, it is enough to us to prove that |SH|/ω(H−SH)<1/2. To clarify expressions, denote by ω0=ω(G−S0)andωH=ω(H−SH). By applying Remark 1, we know that S0=∅, and from Remark 2 and Remark 3 it follows that k≤|S0|.Thus,|S|=|S0|+k|SH|and ω(G◦H−S)= ω0+kωH+|S0|−k. By applying Proposition 5 we know that τ(G◦H)≤1/2, which implies that |S| ω(G◦H−S)=|S0|+k|SH| ω0+kωH+|S0|−k≤1 2, yielding to |SH| ωH≤1 2+ω0−(|S0|+k) 2kωH .(4) 190 On the vulnerability of some families of graphs R. M. Casablanca et al. Since S0=∅because of Remark 1, and k≥1, if S0is not a cutset of Gthen ω0≤1 (i.e., ω0=0ifS0=V(G), and ω0= 1 otherwise). Hence, applying inequality ω0−(|S0|+k)<0in(4),wehave|SH| ωH<1 2.Thus, suppose that S0⊂V(G) is a cutset of G. First assume that |S0|/ω0≥1. This means that ω0−(|S0|+k)< ω0−|S0|≤0, yielding in (4) to |SH| ωH<1 2. Second assume that |S0|/ω0<1. Since S0is a cutset of Gthen it is also a cutset of G◦Hand ω(G◦H−S0)=ω0+|S0|. Therefore, by using that Sis a τ-cut of G◦H, it follows that |S0| ω0+|S0|≥τ(G◦H)= |S0|+k|SH| ω0+kωH+|S0|−k>|S0|+k|SH| ω0+kωH+|S0|.(5) Combining the first and the last members of (5) we deduce that |SH| ωH <|S0| ω0+|S0|=|S0| ω0 1+|S0| ω0 <1 2, because |S0|/ω0<1. This concludes the proof.  From these previous results it follows the next theorem where the toughness of the corona G◦Hof two connected graphs is determined in terms os some parameter of Gand H. Theorem 7 Let G,Hbe two connected graphs of order mand n, respectively. Then the following assertions holds: (i) If τ(G)≥1and τ(H)≥1/2,thenτ(G◦H)=1 2. (ii) If τ(G)<1and τ(H)≥1/2,thenτ(G◦H)= τ(G) 1+τ(G). (iii) If τ(G)≥1and τ(H)<1/2,then τ(G◦H)= min SH∈J(H)1+|SH| 1+ω(H−SH). (iv) If τ(G)<1and τ(H)<1/2,then τ(G◦H)=minτ(G) 1+τ(G),min SH∈J(H) 1+|SH| 1 τ(G)+ω(H−SH)%. 191