On the edge-connectivity and restricted edge-connectivity of a product of graphs
Abstract
The product graph Gm ∗ Gp of two given graphs Gm and Gp was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32–48]. For this kind of graphs we provide bounds for two connectivity parameters and , edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs Gm, Gp of minimum degrees (Gm), (Gp), respectively, we show that (Gm ∗ Gp) is lower bounded by both (Gm) + (Gp) and (Gp) + (Gm), an improvement of what is known for the edge-connectivity of Gm × Gp.
Full text
On the edge-connectivity and restricted edge-connectivity of a product of graphs C. Balbuenaa, M. Cerab, A. Diánezb, P. García-Vázquezb, X. Marcotea aDepartament de Matemàtica Aplicada III, Universitat Politècnica de Catalunya, Barcelona, Spain bDepartamento de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain Received 6 October 2005; received in revised form 28 May 2007; accepted 15 June 2007 Available online 29 June 2007 Abstract The product graph Gm∗Gpof two given graphs Gmand Gpwas defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32–48]. For this kind of graphs we provide bounds for two connectivity parameters and , edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs Gm, Gp of minimum degrees (Gm), (Gp), respectively, we show that (Gm ∗ Gp) is lower bounded by both (Gm) + (Gp) and (Gp) + (Gm),an improvement of what is known for the edge-connectivity of Gm × Gp. Keywords: Edge-connectivity; Restricted edge-connectivity; Permutation graphs; Cartesian product 1. Introduction Ausual objective in network design is the extension of a given interconnection system to a larger and fault-tolerant one so that the communication delay among nodes of the new network is small enough. One interesting model for this kind of extension is a permutation graph—introduced by Chartrand and Harary in [9]—which is simply obtained by taking two disjoint copies of a given graph Gand adding a perfect matching between the two copies. The diameter of a permutation graph has been investigated in [14], whereas [3,13,16–18] are some examples of references where the study of the connectivity of permutation graphs has been addressed. One can naturally wonder if a graph defined similarly from a larger number of copies of G(connecting them somehow) can be still seen as a useful model for the extension of a network under the requirements of small diameter and large connectivity. Such these graphs were introduced a pair of decades ago by Bermond et al. (see [4,5], for example). In this regard, the product graph Gm∗Gp of two given graphs Gm,G p(defined in [4]) can be considered as a natural generalization of a permutation graph, as will be noticed in Section 2. This work deals with such product graphs Gm∗Gp, for which we provide bounds for two connectivity parameters (and , edge-connectivity and restricted edge-connectivity, respectively). Moreover, we present sufficient conditions E-mail addresses: [email protected] (C. Balbuena), [email protected] (M. Cera), [email protected] (A. Diánez), [email protected] (P. García-Vázquez), [email protected] (X. Marcote). 0166-218X/$ - doi:10.1016/j.dam.2007.06.014
C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 2445 to guarantee optimal values of these parameters for product graphs. Our results will be compared with other previous related ones: results for the connectivity of permutation graphs and of cartesian product graphs. Before proceeding, it seems useful to devote Section 2 to recall some basic definitions and to set the notation that will be used in the rest of the paper. In Section 3 we present our results on edge-connectivity and restricted edge-connectivity of a product graph Gm∗Gp, and prove them in Section 4. 2. Terminology and notation We follow [10] for graph-theoretical terminology and notation not defined here. A graph G=(V, E) always means asimple graph (without loops and multiple edges), where V=V (G) is the vertex set and E=E(G) is the edge set. The degree of a vertex vis denoted by d(v) =dG(v), whereas =(G) and =(G) stand for the minimum degree and the maximum degree of G, respectively. For every u∈V, the edge-neighborhood of u is (u) =G(u) ={e∈ E:eis incident with u}. For every uv ∈E, the edge-boundary of uv, denoted by (uv) =G(uv), is the set of edges (uv) =((u) ∪(v)) −uv, and |(uv)|=d(u) +d(v) −2 is called the edge-degree of uv.IfE=∅, then =(G) denotes the minimum edge-degree of G; that is, (G) =min{d(u) +d(v) −2:uv ∈E}. Observe that 2(G) −2⩽(G)⩽(G) +(G) −2. Two distinct edges xy, uv ∈E(G) are called independent if {x,y}∩{u, v}=∅. Amatching is a set of edges that are pairwise independent. A perfect matching between two disjoint graphs G1,G2 with the same order nis a matching consisting of nedges such that each of them has one endvertex in G1and the other one in G2. The diameter of Gis written as D=D(G), which is finite if Gis connected. An edge-cut of a connected graph Gis a set Sof edges such that G−Sis not connected. An edge-cut is called minimal if it does not contain any other edge-cut. An edge-cut is called minimum if no other edge-cut with fewer edges exists; observe that every minimum edge-cut is also minimal. The edge-connectivity of G, denoted by =(G),is the cardinality of a minimum edge-cut, and it is widely known that (G)⩽(G). Even though no edge-cuts exist for K1, the equality (K1)=0 is taken. A connected graph Gis called maximally edge-connected if (G) =(G). In this paper we are also interested in the so-called restricted edge-connectivity =(G), a parameter that was introduced by Esfahanian and Hakimi [12] as follows: =min{|X|:X⊂Eis a restricted edge-cut}, where an edge-cut X⊂Eis called restricted if no vertex uof the graph is such that (u) ⊂X. A restricted edge-cut S of Gis called minimum if no other restricted edge-cut with fewer edges exists, hence |S|=(G). It is readily seen that every minimum restricted edge-cut is a minimal edge-cut. As proved in [12],(G) exists when the connected graph G is not a star and has at least four vertices, in which case (G)⩽(G)⩽(G) holds. When (G) exists, Gis said to be -connected, and Gis called -optimal in case (G) =(G). This parameter can be used to study how connected a graph is in a more accurate manner than only by means of . In fact, (G) > (G) is equivalent to saying that the graph Gis edge-superconnected, i.e., to saying that every minimum edge-cut is equal to the edge-neighborhood of some vertex of minimum degree, see [6,7]. Some sufficient conditions for a graph to be -optimal have been given in terms of the girth in [1,2]. The construction of new graphs from two given ones is not unusual at all. In this regard, Chartrand and Harary introduced in [9] the concept of permutation graph as follows. For a graph Gand a permutation of V (G), the permutation graph G()is defined by taking two disjoint copies of Gand adding a perfect matching joining each vertex vin the first copy to (v) in the second copy. Examples of these graphs include hypercubes, prisms and some generalized Petersen graphs. Later, Bermond et al. [5] introduced the concept of compound graph G[]on the graphs and G. One similar type of compound graph is the product graph of two given graphs, defined in [4] by Bermond et al. in the following way. Definition 1 (Bermond et al. [4]).Let Gm=(V (Gm), E(Gm)) and Gp=(V (Gp), E(Gp)) be two graphs. Let us give an arbitrary orientation to the edges of Gm, in such a way that an arc from vertex xto vertex yis denoted by exy.For each arc exy, let exy be a permutation of V(G p). Then the product graph Gm∗Gphas V(G m)×V(G p)as vertex set, two vertices (x, x),(y, y)being adjacent iff either x=yand xy∈E(Gp)
2446 C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 or exy is an arc and y=exy (x). The product graph Gm∗Gpcan be viewed as formed by |V(G m)|disjoint copies of Gp, each arc exy indicating that some perfect matching between the copies Gx p,Gy p(generated by the vertices xand yof Gm, respectively) is added. So the graph Gmis usually called the main graph and Gpis called the pattern graph of the product graph Gm∗Gp. Moreover, every edge of Gm∗Gpthat belongs to any of the |E(Gm)|perfect matchings between copies of Gpis an intercopy edge of Gm∗Gp. Observe that if we choose exy (x)=xfor any arc exy then Gm∗Gp=Gm×Gp. Furthermore, if Gmis K2we have K2∗G=G(), a permutation graph. Hence, Gm∗Gpcan be considered as a generalized permutation graph. Some relations between the minimum degree, the maximum degree, and the diameter of a product graph Gm∗Gp with the corresponding parameters of its main graph and its pattern graph can be found in [4]. Lemma 2 (Bermond et al. [4]).Let Gmand Gpbe two graphs. Then,for every product graph Gm∗Gp: (i) (Gm∗Gp)=(Gm)+(Gp),(Gm∗Gp)=(Gm)+(Gp). (ii) If both Gmand Gpare connected,then Gm∗Gpis also connected and D(Gm)⩽D(Gm∗Gp)⩽D(Gm)+D(Gp). 3. Results The following proposition is a key point for the rest of our results. In order to present it, some appropriate notation follows (this notation will also be used very often in Section 4). If W⊂E(G) is an edge-cut of a product graph G=Gm∗Gpand Gx pis any given copy in Gof the pattern graph, we will say that Gx pis split byW if both V(H)∩V(G x p)= ∅and V(H∗)∩V(G x p)=∅hold for some two components H,H∗of G−W. Proposition 3. Let Gmand Gpbe two connected graphs,|V(G m)|⩾2, |V(G p)|⩾2. Let W⊂E(G) be a minimal edge-cut of G=Gm∗Gp,and let r denote the number of copies in G of Gpthat are split by W,0⩽r⩽|V(G m)|.The following statements hold: (i) |W|⩾(Gm)|V(G p)|if r=0; |W|⩾((Gm)+1)(Gp)if r⩾(Gm)+1. (ii) |W|⩾r((Gm)+(Gp)−r+1)⩾(Gm)+(Gp)if 1⩽r⩽(Gm). For any two connected graphs Gmand Gp, the inequality (Gm∗Gp)⩽(Gm)+(Gp)holds as a consequence of Lemma 2. When |V(G m)|⩾2 and |V(G p)|⩾2, Proposition 3 allows us to derive a lower bound for (Gm∗Gp), after considering any minimum edge-cut W⊂E(Gm∗Gp)of Gm∗Gp. Moreover, if |V(G m)|=1or|V(G p)|=1itis clear that min{(Gm)|V(G p)|,((Gm)+1)(Gp), (Gm)+(Gp)}=0. Joining together these facts we can write the following theorem. Theorem 4. For every two connected graphs Gmand Gp: min{(Gm)|V(G p)|,((Gm)+1)(Gp), (Gm)+(Gp)}⩽(Gm∗Gp)⩽(Gm)+(Gp). It was proved in [11] that (Gm×Gp)⩾(Gm)+(Gp). Now Theorem 4 allows us to obtain an improvement of this result. Corollary 5. For every two connected graphs Gmand Gp: (Gm∗Gp)⩾min{(Gm)+(Gp), (Gp)+(Gm)}. Further,Gm∗Gpis maximally edge-connected when both Gmand Gpare maximally edge-connected. Another consequence of Theorem 4 is the following corollary, which can be also obtained from the results in [23].
C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 2447 Corollary 6. Let G= K1be a connected graph,and let k⩾0be an integer. Then (Kk+1×G) =min{(k +1)(G), k +(G)}. Now, the result in [16,18] for the edge-connectivity of a permutation graph G()is a direct consequence of Theorem 4 and Corollary 6, when recalling that G()can be written as K2∗Gand that G(id)stands for the cartesian product K2×G(id is the identity permutation). Corollary 7 (Lai [16], Piazza and Ringeisen [18]).Let G be a connected graph. Then,for every permutation of V (G): min{2(G), (G) +1}=(G(id))⩽(G())⩽(G) +1. We can also derive at this point the following important result. Theorem 8. Let Gmand Gpbe two connected graphs. Then the graph Gm∗Gpis maximally edge-connected if any of the following conditions hold: (i) |V(G p)|⩾|V(G m)|⩾2, −2⩽(Gm)−(Gp)⩽2, and (Gp)⩾2. (ii) |V(G m)|=|V(G p)|and (Gm)=(Gp). Corollary 9. For every connected graph G,the graph G∗Gis maximally edge-connected. One may ask whether maximal edge-connectivity can be guaranteed or not for product graphs from earlier known results on the edge-connectivity of a graph. To shed some light on this question, some of the best known sufficient conditions for maximal edge-connectivity of a connected graph are brought together (in chronological order) in the following theorem. Theorem 10. Let G be a connected graph of order n,maximum and minimum degrees and respectively,diameter D and girth g. Then G is maximally edge-connected if any of the following assertions hold: (i) ⩾n/2[8]. (ii) D⩽2[19]. (iii) n>(−1)(D−1+2−2)/(−1)[15]. (iv) ⩾3and n>(−1)((−1)D−1+−3)/(−2)+−1[21]. (v) D⩽g−1if gis odd; g−2if gis even.[21]. Let us compare the results in Theorem 10 with Corollary 9, for any connected graph Gwith (G)⩾2. It is easy to see that the condition in point (i) of Theorem 10 does not hold for any G∗Gsuch that G= K3, and also that G∗G does not satisfy the condition in point (ii) of that theorem if G= Kn. Hence, the usefulness of Corollary 9 is clear with respect to these first two points of Theorem 10. The question is not so simple for the remaining points of Theorem 10, and its applicability to a product graph G∗Gdepends on the actual graph Gand/or the set of perfect matchings between copies of G. For example, consider G=Cn, the cycle of length n⩾3, see Fig. 1.Wehave(Cn∗Cn)=(Cn∗Cn)=4, n/2⩽D(Cn∗Cn)⩽2n/2,g(Cn∗Cn)⩽n, and |V(C n∗Cn)|=n2. Hence, the right-hand side of the inequality in point (iii) of Theorem 10 is not less than 4n/2−1+14. But, as 4n/2−1+14⩾n2easily holds for every n⩾8, n= 9, it turns out that the above referred point (iii) cannot be used to deduce that (Cn∗Cn)=(Cn∗Cn)for these values of the integer n, as Corollary 9 guarantees. Similarly, (Cn∗Cn)=(Cn∗Cn)follows for every n⩾3 from Corollary 9 but does not follow from point (iv) of Theorem 10 when n⩾10. Finally, one can see after some calculations (which compute the maximum possible girth for a 3-regular subgraph of Cn∗Cnconsisting of two cycles Cnand a perfect matching between them) that the inequalities in point
2448 C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 Fig. 1. A graph C4∗C4. (v) of Theorem 10 do not hold when n⩾14, so the usefulness of Corollary 9 for the edge-connectivity of Cn∗Cnis again exhibited. Before approaching the study of the restricted edge-connectivity of a product graph Gm∗Gp, we next present a simple lemma which relates its minimum edge-degree with some parameters of its main graph Gmand its pattern graph Gp. Lemma 11. Let Gmand Gpbe two graphs,both containing some edge. Then,for every product graph Gm∗Gp: 2(Gm)+2(Gp)−2⩽(Gm∗Gp)⩽min{(Gp)+2(Gm), (Gm)+(Gp)+(Gp)}. Theorem 12. Let Gm= K1and Gp= K1be two connected graphs. Then the graph G=Gm∗Gpis -connected and min{(Gm)|V(G p)|,((Gm)+1)(Gp), (Gm)+2(Gp)−1}⩽(G)⩽(G). Shieh proved in [20] that any graph Gm×Gp(except K2×Kn,n⩾2) is edge-superconnected provided that both the connected graphs Gm= K1and Gp= K1are maximally edge-connected regular graphs.As an immediate consequence of Theorem 12, we obtain an improvement of this result for product graphs Gm∗Gpin which the regularity constraint is not necessary. Corollary 13. Let Gmand Gpbe two maximally edge-connected graphs with (Gm)⩾2and (Gp)⩾2. Then the graph Gm∗Gpis edge-superconnected. We next provide bounds for the restricted edge-connectivity of a product graph Gm∗Gp, from which we will be able to give some results for the -optimality of these graphs (see [22] for some related results, for the particular case of cartesian product graphs). Theorem 14. Let Gmand Gp= K3be two connected graphs. If (Gp)⩾(Gm)+1⩾2, then the graph G=Gm∗Gp is -connected and min{(Gm)|V(G p)|,((Gm)+1)(Gp), (Gm)((Gp)+1)+(Gp), (G)}⩽(G)⩽(G). Concerning the restricted edge-connectivity of a permutation graph G()=K2∗G,in[3] was proved that if Gis a connected graph with |V (G)|⩾(G) +2 and (G)⩾2, then any permutation graph G()is -connected and min{2(G), (G) +(G), (G())}⩽(G())⩽(G()). Now, we obtain an improvement of this result as a direct consequence of Theorem 14.
C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 2449 Corollary 15. Let G be a connected graph with |V (G)|⩾(G) +2and (G)⩾2. Then,for every permutation of V (G),the permutation graph G()is -connected and min{2(G), (G) +(G) +1,(G())}⩽(G())⩽(G()). Corollary 16. Let Gmand Gpbe two connected graphs. If (Gp)⩾(Gm)+1⩾2, (Gm)|V(G p)|⩾(Gp)+2(Gm) and (Gp)+(Gm)⩾(Gp)+2, then the graph G=Gm∗Gpis -connected and (G) =(G). Corollary 17. Let G be a connected graph,with (G)⩾3and (G)⩽2(G) −1. Then,the graph G∗(G ∗G) is -connected and (G ∗(G ∗G)) =(G ∗(G ∗G)). 4. Proofs For the following proofs, it must be recalled that the inequality a·b⩾a+b−1 holds for any pair of integers a,b⩾1. Proof of Proposition 3. Because Wis minimal we have that G−Wconsists of exactly two connected components, Hand H∗. Observe that |W|⩾r(Gp)holds, because at least (Gp)edges must be deleted from Gin order to split (by W) each of the considered rcopies of Gp. (i) If r⩾(Gm)+1 then |W|⩾((Gm)+1)(Gp)follows directly. Suppose now that r=0. Then all the edges in W are intercopy edges and correspond to t⩾1 perfect matchings between copies of Gpthat appear in Gas a replacement of tedges of Gm. Moreover, the set of these tedges of Gmmust be an edge-cut of Gm(for if not, G−Wis still connected), hence t⩾(Gm). Thus |W|⩾(Gm)|V(G p)|. (ii) Let V(G m)={x1,x 2,...,x n}. Without loss of generality, assume that the rsplit (by W) copies of Gpare Gx1 p,G x2 p,...,G xr pcorresponding to vertices x1,x 2,...,x rof Gm,1⩽r⩽(Gm). For every j=1,...,r, let us write V(G xj p)=Vj∪V∗ j, with Vj⊂V(H),V∗ j⊂V(H∗), and let us denote kj=min{|Vj|,|V∗ j|}; moreover, let us call sj to the number of edges of Gxj pjoining vertices in Vjto vertices in V∗ j. Taking into account that each xj(j=1,...,r) is adjacent in Gmto at least (Gm)−(r −1)other vertices xqof Gm,q⩾r+1, then from copy Gxj pwe have at least as many edges in Was kj((Gm)−(r −1)) +sj. Thus we obtain |W|⩾ r j=1 (kj((Gm)−(r −1)) +sj). (1) Let us study the terms of the above sum according to the value of kj. If kj⩾(Gp), using that sj⩾(Gp)⩾1wehave kj((Gm)−r+1)+sj⩾kj+(Gm)−r+sj⩾(Gp)+(Gm)−r+1. (2) If kj⩽(Gp)−1, assuming without loss of generality that kj=|V∗ j|, we can write kj(kj−1)⩾ u∈V∗ j dGxj p(u) −sj⩾kj(Gp)−sj, hence sj⩾kj((Gp)−kj+1). (3) Therefore, from (3) we have kj((Gm)−r+1)+sj⩾kj((Gm)+(Gp)−r−kj+2)⩾(Gm)+(Gp)−r+1, (4) because when kj∈{1,...,(Gp)−1}it is not difficult to see that the middle term of the above chain of inequalities takes its minimum value when kj=1. Hence, from (1), (2) and (4) it follows |W|⩾r((Gm)+(Gp)−r+1). (5)
2450 C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 Since the minimum value for the right-hand side of (5) is taken when r=1, we have finally that |W|⩾r((Gm)+(Gp)−r+1)⩾(Gm)+(Gp), ending the proof. Proof of Corollary 5. The claimed inequality easily holds when |V(G m)|=1or|V(G p)|=1, that is to say, when (Gm)=(Gm)=0or(Gp)=(Gp)=0. Hence, suppose (Gm)⩾1 and (Gp)⩾1 from now on. Taking into account that |V(G p)|⩾(Gp)+1, we have (Gm)|V(G p)|⩾(Gm)((Gp)+1)⩾(Gm)+(Gp), ((Gm)+1)(Gp)⩾(Gm)+(Gp), (Gm)+(Gp)⩾min{(Gm)+(Gp), (Gp)+(Gm)}. Hence the inequality follows directly from Theorem 4. Furthermore, as a consequence, (Gm∗Gp)=(Gm)+(Gp) holds provided that (Gm)=(Gm)and (Gp)=(Gp). Proof of Corollary 6. When k=0 it is clear that Kk+1×G=K1×G=G, hence (Kk+1×G) =(G) and the result follows. Then, assume that k⩾1. We have (Kk+1)=(Kk+1)=kand |V (G)|⩾(G) +1, and then (Kk+1)|V (G)|⩾k((G) +1)⩾(G) +k. Therefore, following Theorem 4, we can write k+(G)⩾(Kk+1×G)⩾min{(k +1)(G), k +(G)}⩾2, the last inequality being a consequence of k⩾1 and G= K1. The result clearly follows when k+(G)⩽(k +1)(G), hence we can suppose (k +1)(G)⩽k+(G). To end the proof it suffices to show that there exists in Kk+1×Gan edge-cut Wsuch that |W|=(k +1)(G). Let W⊂E(G) be a minimum edge-cut of the pattern graph, | W|=(G). Let V(K k+1)={x1,x 2,...,x k+1}, and let W1,W 2,...,W k+1be the corresponding copies of Win Gx1,G x2,...,G xk+1, respectively. Then, W1∪W2∪···∪Wk+1 is clearly an edge-cut of Kk+1×G, of cardinality |W1∪W2∪···∪Wk+1|=(k +1)(G). Proof of Theorem 8. Let =min{(Gm), (Gp)}. Observe that (Gm∗Gp)=(Gm)+(Gp)⩽2+2 for both cases (i), (ii), and also that |V(G p)|⩾1+(Gp)⩾1+. (i) As (Gp)⩾2 by hypothesis, we have ((Gm)+1)(Gp)⩾2(+1)⩾(Gm)+(Gp). (6) Now, we claim that (Gm)|V(G p)|⩾(Gm)+(Gp), (7) with (Gm)⩾1 because Gm= K1. Indeed, when (Gm)⩾2 we obtain (Gm)|V(G p)|⩾2(1+)⩾(Gm)+(Gp), so (7) holds. Inequality (7) also holds clearly if (Gm)=1 because (Gm)|V(G p)|⩾|V(G p)|⩾1+(Gp)=(Gm)+(Gp). Hence, suppose that 1 =(Gm)<(Gm), so from item (i) of Theorem 10 we get |V(G m)|⩾2(Gm)+2⩾2+2. Recalling the hypothesis |V(G p)|⩾|V(G m)|,wehave (Gm)|V(G p)|=|V(G p)|⩾2+2⩾(Gm)+(Gp), and (7) is again true. Thus, from (6), (7) and from Theorem 4 it follows that (Gm∗Gp)=(Gm)+(Gp).
C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 2451 (ii) In this case, =(Gm)=(Gp), and we want to prove that (Gm∗Gp)=2. When |V(G m)|=|V(G p)|=1, both Gmand Gpare equal to the graph K1, hence Gm∗Gp=K1and the result is obvious. So Gm= K1and Gp= K1must be assumed. Moreover from Corollary 5 it follows (Gm∗Gp)=2if =1, so assume that ⩾2. Furthermore, the previous item (i) allows us to assume also that (Gp)=1, which in turn yields |V(G m)|=|V(G p)|⩾2(Gp)+2=2+2 as a consequence of point (i) of Theorem 10. Let W⊂E(Gm∗Gp)be any minimum edge-cut of Gm∗Gp,|W|=(Gm∗Gp), and let H,H∗be the two connected components of (Gm∗Gp)−W. Let rdenote the number of split (by W) copies of Gpin Gm∗Gp. Following Proposition 3wehave|W|⩾(Gm)|V(G p)|=(Gm)|V(G m)|>2when r=0, and also |W|⩾(Gm)+(Gp)=2if 1⩽r⩽. Moreover, if r⩾2then the inequality |W|⩾2holds because clearly |W|⩾r. Hence, suppose that +1⩽r⩽2−1, and assume that the rconsidered split copies of Gpare Gx1 p,G x2 p,...,G xr p (corresponding to vertices x1,x 2,...,x rof Gm). As |V(G m)|⩾2+2 and r⩽2−1, there must exist some vertex xk∈V(G m),k>r, such that xkis adjacent to some vertex in {x1,x 2,...,x r}, say to x1. As in Proposition 3 we write V(G xj p)=Vj∪V∗ j, with Vj⊂V(H),V∗ j⊂V(H∗)(for j=1,...,r), and denote by sjthe number of edges of Gxj p joining vertices in Vjto vertices in V∗ j. Since Wcontains all the edges connecting vertices in Gxk pwith vertices in V1, or Wcontains all the edges connecting vertices in Gxk pwith vertices in V∗ 1, then the set of edges Wcontains at least k1=min{|V1|,|V∗ 1|} edges that are incident with vertices of Gxk p.Ifk1⩽−1, then reasoning as in Proposition 3 we have that s1⩾k1(−(k1−1))⩾, because the minimum is attained for k1=1. Hence we obtain |W|⩾k1+s1+ r j=2 sj⩾k1++r−1>2, because r⩾+1. And if k1⩾then |W|⩾k1+ r j=1 sj⩾+r⩾2+1>2. Then, we have shown that |W|⩾2in any case, and the proof of (ii) is complete. Proof of Lemma 11. Observe that (Gm),(Gp)and (Gm∗Gp)can be defined, because E(Gm)=∅,E(Gp)=∅, and so E(Gm∗Gp)=∅. Notice also that the lower bound for (Gm∗Gp)follows easily because (Gm∗Gp)⩾2(Gm∗ Gp)−2=2(Gm)+2(Gp)−2 from Lemma 2. For the upper bound, consider first some edge yy∈E(Gp)such that |Gp(yy)|=(Gp), and let x∈V(G m)be a vertex such that dGm(x) =(Gm). Taking u=(x, y) and v=(x, y), it turns out that uv ∈E(Gm∗Gp)hence we can write (Gm∗Gp)⩽|Gm∗Gp(uv)|=|Gp(yy)|+2(Gm)=(Gp)+2(Gm). Second, let xx∈E(Gm)be an edge such that |Gm(xx)|=(Gm), and let y∈V(G p)be a vertex such that dGp(y) =(Gp). Consider the intercopy edge uv ∈E(Gm∗Gp)with u=(x, y) and v=(x,y). Hence (Gm∗Gp)⩽|Gm∗Gp(uv)|=|Gm(xx)|+dGp(y) +dGp(y)⩽(Gm)+(Gp)+(Gp), and the proof is complete. Proof of Theorem 12. Observe that |V(G m)|⩾2 and |V(G p)|⩾2 implies |V (G)|⩾4. Besides, Gis not a star because (G) =(Gm)+(Gp)⩾2, hence Gis -connected and (G)⩽(G). Let W⊂E(G) be any minimum restricted edge-cut and let H,H∗be the two connected components of G−W. Let rdenote the number of split copies of Gpin Gm∗Gp. Proposition 3 provides the corresponding lower bounds for |W|when r=0 and also when r⩾(Gm)+1. Again from Proposition 3 we get |W|⩾r((Gm)+(Gp)−r+1)if 2⩽r⩽(Gm). Now the minimum of r((Gm)+(Gp)−r+1)is attained for r=2 when 2⩽r⩽(Gm), thus we deduce that |W|⩾2((Gm)+(Gp)−1)in this case.
2452 C. Balbuena et al. / Discrete Applied Mathematics 155 (2007) 2444–2455 Suppose that r=1 from now on, and assume that the considered split copy of Gpis Gx1 p(corresponding to vertex x1 of Gm). Let V(G x1 p)=V1∪V∗ 1be such that V1⊂V(H)and V∗ 1⊂V(H∗), and let s1be the number of edges joining vertices in V1with vertices in V∗ 1.Nowif1is the number of edges of Gmthat join x1with vertices xjwhose copy Gxj pin Gis contained in H∗, then we have (G) =|W|⩾|V1|1+|V∗ 1|(dGm(x1)−1)+s1. (8) First suppose that 1=0. This means that all copies Gxj pcorresponding to neighbors xjof x1in Gmare contained in H, which implies |V∗ 1|⩾2 because Wis a restricted edge-cut. Moreover, if |V∗ 1|⩾(Gp)+1 then, taking into account that s1⩾(Gp),weget |W|⩾|V∗ 1|(Gm)+s1⩾((Gp)+1)(Gm)+(Gp)>((Gm)+1)(Gp), and the result follows. So assume that 2⩽|V∗ 1|⩽(Gp). Reasoning as in Proposition 3, we have that s1⩾|V∗ 1|((Gp)− |V∗ 1|+1). Hence we obtain |W|⩾|V∗ 1|((Gm)+(Gp)−|V∗ 1|+1)⩾2((Gm)+(Gp)−1), and we are done. Second suppose that 1=dGm(x1). In this case (8) becomes |W|⩾|V1|(Gm)+s1and |V1|⩾2 because Wis a restricted edge-cut. In a similar way as for 1=0 we obtain again |W|⩾2((Gm)+(Gp)−1), and the result holds. Finally suppose that 1⩽1⩽dGm(x1)−1. In this case, it follows from (8) that (G) =|W|⩾|V1|+1+|V∗ 1|+dGm(x1)−1−2+s1⩾|V(G p)|+(Gm)+(Gp)−2. Now if |V(G p)|⩽2(Gp)+1 then (Gp)=(Gp)by Theorem 10 (i), and as |V(G p)|⩾(Gp)+1weget (G) =|W|⩾(Gm)+2(Gp)−1, and we have finished. If |V(G p)|⩾2(Gp)+2 then (G) =|W|⩾(Gm)+2(Gp)+(Gp), which completes the proof. Proof of Theorem 14. ObservethatGm= K1because (Gm)⩾1. So(G)=(Gm)+(Gp)⩾3 and|V (G)|⩾(G)+ 1⩾4, hence Gis -connected and (G)⩽(G). Notice also that (Gp)⩾2 and Gp= K3implies that Gpis not a star and its order is at least four, hence (Gp)exists. Let W⊂E(G) be a minimum restricted edge-cut of G,|W|=(G). Thus G−Whas no isolated vertex and consists of exactly two connected components, Hand H∗.IfV(G m)={x1,...,x n}we write W=W1∪···∪Wn∪Wcc, where Wj⊂E(Gxj p)for each j∈{1,...,n}, and Wcc is only composed by intercopy edges. Clearly, if Wj=∅then Wjis an edge-cut of Gxj pbecause Whas minimum cardinality. First, let us suppose that one of the components of G−W, say H, consists of the subgraph induced by one vertex u=(xj,y)∈V(G xj p)plus a number of qneighbors v1,...,v qin V (G)\V(G xj p),1⩽q⩽dGm(xj)(observe that q= 0, because ucannot be isolated in G−W), such that dH(vi)=1 for each i∈{1,...,q}. With this structure for H,we have |W|⩾dGp(y) +(dG(v1)−1)+ q i=2 (dG(vi)−1)+(dGm(xj)−q).