On super edge-connectivity of product graphs

On super edge-connectivity of product graphs

Applied Mathematics and Computation 207 (2009) 300–306 Contents lists available at ScienceDirect Applied Mathematics and Computation journal homepag...

204KB Sizes 1 Downloads 23 Views

Applied Mathematics and Computation 207 (2009) 300–306

Contents lists available at ScienceDirect

Applied Mathematics and Computation journal homepage: www.elsevier.com/locate/amc

On super edge-connectivity of product graphs q Min Lü a,*, Guo-Liang Chen a, Xi-Rong Xu b a

Anhui Province-Most Key Co-Lab of High Performance Computing and Its Applications, Department of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui 230026, China Department of Computer Science, Dalian University of Technology, Dalian 116024, China

b

a r t i c l e

i n f o

Keywords: Super edge-connectivity Super edge-connected k0 -graph k0 -optimal Product graph

a b s t r a c t For a connected graph G, the super edge-connectivity k0 ðGÞ is the minimum cardinality of an edge-cut F in G such that G  F contains no isolated vertices. It is a more refined index than the edge-connectivity for the fault-tolerance of the network modeled by G. This paper deals with the super edge-connectivity of product graphs G1 G2 , which is one important model in the design of large reliable networks. Let Gi be a connected graph with order mi and edge-connectivity ki for i ¼ 1; 2. We show that k0 ðG1 G2 Þ P minfm1 k2 ; m2 k1 ; k1 þ 2k2 ; 2k1 þ k2 g for m1 ; m2 P 2 and deduce the super edge-connectedness of G1 G2 when G1 and G2 are maximally edge-connected with dðG1 Þ P 2; dðG2 Þ P 2. Furthermore we state sufficient conditions for G1 G2 to be k0 -optimal, that is, k0 ðG1 G2 Þ ¼ nðG1 G2 Þ. As a consequence, we obtain the k0 -optimality of some important interconnection networks. Crown Copyright Ó 2008 Published by Elsevier Inc. All rights reserved.

1. Introduction For the graph theoretical terminology and notation not defined here, we refer the reader to [26]. Throughout this paper, a graph G ¼ ðV; EÞ always means a finite undirected graph without self-loops or multiple edges, where V ¼ VðGÞ is the vertexset and E ¼ EðGÞ is the edge-set. For any edge uv 2 E, the parameter nG ðuv Þ ¼ dG ðuÞ þ dG ðv Þ  2 is the degree of the edge uv and the parameter nðGÞ ¼ minfnG ðuv Þjuv 2 Eg is the minimum edge-degree of G. For X # V, let EG ðXÞ be the set of those edges with one end-point in X and the other in V  X. The symbols K 1;n1 and K n denote a star graph and a complete graph of order n, respectively. It is well-known that when the underlying topology of an interconnection network is modeled by a connected graph G ¼ ðV; EÞ, where V is the set of processors and E is the set of communication links in the network, the edge-connectivity kðGÞ of G is an important measurement of the reliability and the fault-tolerance of the network, that is to say, of the ability of the interconnection system to work even if some links fail. In general, the larger kðGÞ is, the more reliable the network is. It is well-known that kðGÞ 6 dðGÞ, where dðGÞ is the minimum degree of G. A connected graph G is said to be maximally edgeconnected if kðGÞ ¼ dðGÞ. A graph G is said to be super edge-connected (in short, super-k) if G is maximally edge-connected and every minimum edge-cut isolates a vertex of G. It has been shown that a super edge-connected network is the most reliable and has the smallest edge failure rate among all the networks with the same edge-connectivity (see, for example, [30,31]).

q Key project supported by National Natural Science Foundation of China (No. 60533020), and supported by NNSF of China (Nos. 10671191 and 10701068). * Corresponding author. E-mail address: [email protected] (M. Lü).

0096-3003/$ - see front matter Crown Copyright Ó 2008 Published by Elsevier Inc. All rights reserved. doi:10.1016/j.amc.2008.10.035

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

301

To measure accurately how reliable a super edge-connected graph is after the deletion of a set of edges, we propose the concept of super edge-connectivity, introduced first by Fiol et al. in [11]. The parameter is also called as restricted edge-connectivity in some references, such as [10]. An edge-cut F is called a super edge-cut of G if G  F contains no isolated vertices. In general, super edge-cuts do not always exist. The super edge-connectivity k0 ðGÞ is the minimum cardinality of a super edge-cut in G if super edge-cuts exist, and, by convention, is þ1 otherwise. The new parameter k0 in conjunction with k can provide more accurate measures for the fault-tolerance of a large-scale parallel processing system and, thus, has received the attention of many researchers in recent years (see, for example, [7– 18,20–22,27,28]). Esfahanian and Hakimi [10] showed that if G is neither K 1;n1 nor K 3 , then

kðGÞ 6 k0 ðGÞ 6 nðGÞ:

ð1Þ

A connected graph G is called a k0 -graph if G is neither K 1;n1 nor K 3 . It is easy to see that G is super edge-connected if and only if k0 ðGÞ > kðGÞ. A super-k graph G is said to be optimally super edge-connected (in short, k0 -optimal) if k0 ðGÞ ¼ nðGÞ. A k0 -optimal graph is not always super edge-connected. Take C n as an example. k0 ðC n Þ ¼ 2 ¼ nðC n Þ, so C n is k0 -optimal; but it is not super edge-connected for k0 ðC n Þ ¼ 2 ¼ kðC n Þ. Several sufficient conditions for a graph to be maximally edge-connected, super edgeconnected or k0 -optimal have been given in the literature (see, for example, [3,6,13,19,20,22,23]). Recently, Chiue and Shieh [8] have given some sufficient conditions for the Cartesian product G1  G2 to be super-k; Shieh [21] has proved that G1  G2 is super-k if both G1 and G2 are regular and maximally edge-connected except for K 2  K n , where n P 2. Ueffing and Volkmann [24] have investigated the k0 -optimality of G1  G2 when both G1 and G2 are k0 -optimal. Li and Xu [14] have determined k0 ðK 2  GÞ ¼ minfn; 2dðGÞ; 2k0 ðGÞg for any connected graph G with n vertices. Balbuena et al. [1] have studied the restricted connectivity of permutation graphs. This paper will investigate the super edge-connectivity of a class of interconnection networks modeled by product graphs, which contains Cartesian product graphs and permutation graphs as special classes. We provide the bounds for the super edge-connectivity of product graphs and state sufficient conditions that guarantee the product graphs to be k0 -optimal. As a consequence, we generalize the result of Shieh [21] on the super edge-connectedness of the Cartesian product of two regular graphs with maximum edge-connectivity and deduce k0 -optimality of many networks. 2. Preliminaries It is well-known that Cartesian product method is an effective method for constructing a large graph from several smaller ones (hence, for designing large-scale interconnection networks) with certain desirable properties (such as regularity) remained. What’s more, a number of parameters can be easily calculated from the corresponding parameters for those small initial graphs. Thus, in this work we will deal with a generalization of the Cartesian product graphs, the product graph G1  G2 , introduced by Bermond et al. [4,5]. Definition. Let G1 ¼ ðV 1 ; E1 Þ and G2 ¼ ðV 2 ; E2 Þ be two graphs. For each edge xx0 2 E1 , let pxx0 be a permutation of V 2 . Then the product graph G1 G2 has V 1  V 2 as vertex-set, with two vertices ðx; yÞ; ðx0 ; y0 Þ being adjacent if and only if either

x ¼ x0

and yy0 2 E2

or

xx0 2 E1

and y0 ¼ pxx0 ðyÞ:

It is worth pointing out that G1 G2 is not uniquely determined by G1 and G2 , but also the permutations pxx0 for each edge xx0 of G1 . So, when we speak of any result on G1  G2 , we means it holds for any product graph composed by G1 and G2 . Obviously, we have G1 G2 ¼ G1  G2 by choosing pxx0 ðyÞ ¼ y for any edge xx0 2 E1 . Note that product of two graphs does not satisfy the commutative law, in sense of isomorphism, while Cartesian product does. For a graph G and a permutation p of VðGÞ, the permutation graph or generalized prism GðpÞ is defined by taking two disjoint copies of G and a matching joining each vertex v in the first copy to pðv Þ in the second copy, which is a product graph as GðpÞ ¼ K 2 G. Thus, G1 G2 can be considered as a generalized permutation graph. For convenience, we define subgraphs G2x of G1 G2 as follows. For any x 2 V 1 ,

VðG2x Þ ¼ fðx; yÞjy 2 V 2 g; EðG2x Þ ¼ fðx; y1 Þðx; y2 Þjy1 y2 2 E2 g: It is clear that G2x is isomorphic to G2 for any x 2 V 1 . The product graph G1 G2 can be viewed as formed by jV 1 j disjoint copies of G2 , each edge xx0 2 E1 , indicating that some perfect matching between the copies G2x and G2x0 is added. So the graph G1 is usually called the main graph and G2 is called the pattern graph of the product graph G1 G2 . Moreover, every edge of G1 G2 that belongs to any of the jE1 j perfect matchings between copies of G2 is a cross edge of G1 G2 . Denote the set of those cross edges by M. Some relations between the minimum degree, the maximum degree, and the diameter, connectivity of a product graph G1 G2 with the corresponding parameters of its main graph and its pattern graph can be found in [2,4].

302

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

Let

V 2x ¼ VðG2x Þ;

E2x ¼ EðG2x Þ:

Then for any x; x0 2 V 1 with x–x0 ,

E2x \ E2x0 ¼ ;;

and E2x \ M ¼ ;;

EðG1 G2 Þ ¼ M [ ð[x2V 1 E2x Þ: For F # EðG1 G2 Þ, let

G02x ¼ G2x  F

for any x 2 V 1 :

Then, it is clear that VðG02x Þ ¼ V 2x and EðG02x Þ ¼ E2x n F for any x 2 V 1 . Throughout this paper, we always assume that Gi have mi vertices, respectively, and kðGi Þ ¼ ki P 1 for i ¼ 1; 2. In Section 3, we provide bounds for k0 ðG1 G2 Þ and investigate the k0 -optimality of G1 G2 in Section 4. 3. Bounds for k0 ðG1 G2 Þ Theorem 3.1. For two connected graphs G1 and G2 with

m1 P 2 and m2 P 2:

minfm1 k2 ; m2 k1 ; k1 þ 2k2 ; 2k1 þ k2 g 6 k0 ðG1 G2 Þ 6 minfm2 k1 ; nðG1  G2 Þg: Proof. Denote G ¼ G1 G2 . Suppose B ¼ EG1 ðXÞ is a minimum edge-cut of G1 , where X # V 1 . Then G1  B contains exactly two components, that is, two subgraphs G1 ½X and G1 ½V 1  X induced by X and V 1  X, respectively. Hence, B0 ¼ EG ðX  V 2 Þ is an edge-cut of G1 G2 . The two components of G  B0 are subgraphs G½X  V 2  and G½ðV 1  XÞ  V 2 , both of which have at least two vertices. So B0 is a super edge-cut of G, which means k0 ðGÞ 6 jB0 j ¼ m2 k1 . By (1), k0 ðGÞ 6 nðGÞ. Thus, k0 ðG1 G2 Þ 6 minfm2 k1 ; nðG1 G2 Þg. Denote l ¼ minfm1 k2 ; m2 k1 ; k1 þ 2k2 ; 2k1 þ k2 g. Assume F is a minimum super edge-cut with jFj < l. Since jFj < l 6 m1 k2 , there exists some x0 2 V 1 such that G02x0 is connected. To deduce a contradiction, it suffices to show that any vertex of G02x is connected to G02x0 in G  F for any x–x0 . Since there are at least k1 edge-disjoint paths between x and x0 in G1 by Menger’s Theorem, there are at least m2 k1 edgedisjoint paths connecting the two copies G2x and G2x0 in G. If G02x is connected in G  F, then any vertex of G02x is connected to G02x0 , because jFj < m2 k1 . If G02x is disconnected in G  F, then jF \ E2x j P k2 . For any vertex v of G02x , suppose it is contained in a component H of G02x . If jVðHÞj P 2, then there are at least jVðHÞjk1 P 2k1 edge-disjoint paths from VðHÞ to V 2x0 in G. Because jFj < k2 þ 2k1 , vertex v is connected to G02x0 in G  F. If jVðHÞj ¼ 1, then vertex v is adjacent to some vertex of another copy of G2 , say v 0 , in G  F for F is a super edge-cut. Without loss of generality, assume vertex v 0 2 V 2x1 , where x1 –x. If x1 ¼ x0 , then we are done. In the following, we assume x1 –x0 . If G02x1 is connected in G  F, then G02x1 is connected to G02x0 in G  F, otherwise jFj P m2 k1 , a contradiction. Hence, in G  F, the vertex v is connected to G02x0 via vertex v 0 of G02x1 . If G02x1 is disconnected in G  F, then jF \ E2x1 j P k2 . Note that there are at least k1 edge-disjoint paths from vertex v to V 2x0 in G. Since jFj < k1 þ 2k2 , vertex v is connected to G02x0 in G  F. To sum up, any vertex v of G02x is connected to G02x0 for any x–x0 . The contradiction implies k0 ðGÞ P minfm1 k2 ; m2 k1 ; k1 þ 2k2 ; 2k1 þ k2 g. The theorem holds. h Corollary 3.1. If Gi are maximally edge-connected with dðGi Þ P 2, then G1 G2 is super edge-connected. Proof. For convenience, denote kðGi Þ ¼ ki and dðGi Þ ¼ di for i ¼ 1; 2. Note that kðG1 G2 Þ 6 dðG1 G2 Þ ¼ d1 þ d2 . Since d1 P 2 and d2 P 2, we have

m1 k2 P ðd1 þ 1Þk2 ¼ ðd1 þ 1Þd2 ¼ d1 d2 þ d2 > d1 þ d2 ; m2 k1 P ðd2 þ 1Þk1 ¼ ðd2 þ 1Þd1 ¼ d1 d2 þ d1 > d1 þ d2 ; k1 þ 2k2 ¼ d1 þ 2d2 > d1 þ d2 ; 2k1 þ k2 ¼ 2d1 þ d2 > d1 þ d2 : By Theorem 3.1, it follows that k0 ðG1 G2 Þ > kðG1 G2 Þ, which means G1 G2 is super edge-connected.

h

Corollary 3.1 can be seen as a generalization of one result in [8,21], which states that the Cartesian product of two regular maximally edge-connected graphs is super edge-connected except for K 2  K n with n P 2. The corollary holds not only for G1  G2 but for G1 G2 , and regularity needs not be assumed for graphs G1 and G2 . Both of the two conditions dðG1 Þ P 2 and dðG2 Þ P 2 are indispensable. The Cartesian product graph K 2  K n is just one example. A more general example in this regard is G ¼ G0 K m , where m P 2 and G0 is a connected graph of order n with kðG0 Þ ¼ dðG0 Þ ¼ 1. To see that the maximally edgeconnected graph G is not super edge-connected, we only need to take two adjacent vertices e ¼ x1 x2 2 EðG0 Þ such that

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

303

dG0 ðx1 Þ ¼ 1, and see that F ¼ EG ðfx1 g  VðK m ÞÞ is an edge-cut of G with jFj ¼ m ¼ dðGÞ whose deletion from G does not isolate any vertex. In addition, we deduce that k0 ðGÞ 6 jFj ¼ m. Applying Theorem 3.1, k0 ðGÞ P minfnðm  1Þ; m; 2m  1; m þ 1g ¼ m. So k0 ðGÞ ¼ m, and the lower bound given by Theorem 3.1 is attained. The following theorem establishes the lower bound of k0 ðG1 G2 Þ when G1 or G2 is a complete graph. Theorem 3.2. Suppose one of G1 and G2 is a complete graph of order m P 2 and that the other graph is k-edge-connected with nðP 2Þ vertices. Then

k0 ðG1 G2 Þ P minfnðm  1Þ; mk; 2k þ 2m  4g: Proof. Denote G ¼ G1 G2 . Clearly, the graph G has jVðGÞj ¼ mn P 4 vertices for m P 2 and n P 2. And dðGÞ ¼ dðG1 Þ þ dðG2 Þ P 2. That is, G is neither K 3 nor a star graph and thus, the super edge-connectivity k0 ðGÞ is well defined. Denote l ¼ minfnðm  1Þ; mk; 2k þ 2m  4g. Let F be a minimum super edge-cut of G with jFj ¼ k0 ðGÞ < l. Because jFj < minfnðm  1Þ; mkg 6 jV 1 jkðG2 Þ, there exists at least one copy of G2 which is connected in G  F, denoted by G02x0 . Due to the minimality of F, G  F consists of two exactly two components. Suppose H is one component of G  F such that G02x0  H. To obtain a contradiction, it suffices to show that the component H is connected to G02x0 in G  F. Denote S ¼ fx 2 V 1 jV 2x \ VðHÞ–;g. Then jSj 6 jVðG1 Þj  1. Since there are at least kðG1 Þ edge-disjoint xx0 -paths in G1 , there are at least jVðG2 ÞjkðG1 Þ edge-disjoint paths connecting the two corresponding copies G2x and G2x0 in G. If G02x is connected in G  F for some x 2 S, then it is connected to G02x0 because jFj < minfnðm  1Þ; mkg 6 jVðG2 ÞjkðG1 Þ, by which we derive that H is connected to G02x0 . Then we only need to prove that H is connected to G02x0 while G02x is disconnected in G  F for any x 2 S. We distinguish the following two cases since K m G2 À G2 K m . Case 1. G1 ¼ K m . Here kðG1 Þ ¼ m  1 and kðG2 Þ ¼ k. Suppose there exists one vertex u 2 VðHÞ \ V 2x that is not isolated in G02x . The hypothesis G02x is disconnected implies jF \ E2x j P kðG2 Þ ¼ k. Let H0 be the component of G02x containing u and let t ¼ jVðH0 Þj. Then t P 2. There are at least tðm  1Þ edge-disjoint paths connecting H0 with G2x0 in G because there are at least m  1 edge-disjoint xx0 -paths in G1 . If t P k, then the vertex u is connected to G02x0 in G  F, otherwise jFj P jF \ E2x j þ tðm  1Þ P k þ kðm  1Þ ¼ mk, a contradiction. If t < k, then 2 6 t 6 dðG2 Þ  1 and thus dðG2 Þ P 3. Every vertex of H0 has at least dðG2 Þ  ðt  1Þ neighbors in V 2x n VðH0 Þ, so

jF \ E2x j P EG2x ðVðH0 ÞÞ P ðdðG2 Þ  ðt  1ÞÞt ¼ t2 þ ðdðG2 Þ þ 1Þt: Define a function f ðtÞ ¼ t2 þ ðdðG2 Þ þ 1Þt. It is easy to see the function f ðtÞ reaches the minimum value at an end-point of the interval ½2; dðG2 Þ  1. Since f ð2Þ ¼ f ðdðG2 Þ  1Þ ¼ 2dðG2 Þ  2, we obtain that

f ðtÞ ¼ t2 þ ðdðG2 Þ þ 1Þt P 2dðG2 Þ  2: If u is not connected to

G02x0

ð2Þ

in G  F, then we obtain a contradiction as follows:

jFj P jF \ E2x j þ jF \ Mj P 2dðG2 Þ  2 þ tðm  1Þ P 2k  2 þ 2ðm  1Þ ¼ 2k þ 2m  4: Now we assume that every vertex u 2 VðHÞ \ V 2x is an isolated vertex of G02x . Since F is a super edge-cut, vertex u is adjacent to some vertex which is in another copy of G2 . Then 2 6 s ¼ jSj 6 m  1 and thus m P 3. Because G1 ¼ K m , we have that jEG1 ðSÞj ¼ sðm  sÞ. Then vertex u is connected to G02x0 in G  F, otherwise

jFj P

X x2S

jF \ E2x j þ jF \ Mj P

X

dðG2 Þ þ sðm  sÞ P

x2S

X

k þ sðm  sÞ ¼ sk þ sðm  sÞ ¼ s2 þ ðm þ kÞs:

x2S

The function gðsÞ ¼ s2 þ ðm þ kÞs reaches the minimum value at an end-point of the interval ½2; m  1 and gð2Þ ¼ 2k þ 2m  4 and gðm  1Þ ¼ ðm  1Þk þ m  1 ¼ 2k þ ðm  3Þk þ m  1 P 2k þ m  3 þ m  1 ¼ 2k þ 2m  4, so

gðsÞ ¼ s2 þ ðm þ kÞs P 2k þ 2m  4;

ð3Þ

which implies a contradiction jFj P 2k þ 2m  4. Case 2. G2 ¼ K m . Here kðG1 Þ ¼ k and kðG2 Þ ¼ m  1. We take the similar technique as Case 1 with a little difference. In the same way, we first consider such a case that there is at least a vertex u 2 VðHÞ \ V 2x which is not isolated in G02x . That is, vertex u is contained in a component H0 of G02x with at least two vertices. That is, s ¼ jVðH0 Þj P 2. The fact that G02x is disconnected means s 6 m  1, and thus m P 3. There are at least skðG1 Þ ¼ sk edge-disjoint paths connecting H0 with G2x0 in G. Any two vertices of G2x are adjacent, so jF \ E2x j P sðm  sÞ. Therefore, vertex u is connected to G02x0 in G  F, otherwise jFj P sðm  sÞ þ sk ¼ s2 þ ðm þ kÞs P 2k þ 2m  4 by (3). In the following we assume every vertex u 2 VðHÞ \ V 2x is an isolated vertex of G02x . The vertex u must be adjacent to another copy of G2 because F is a super edge-cut. Thereby, t ¼ jSj P 2. Here jF \ E2x j P dðG2 Þ ¼ m  1 for any x 2 S.

304

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

Assume t P k. There exist at least k edge-disjoint xx0 -paths in G1 , so jF \ Mj P k. The vertex u is connected to G02x0 in G  F, P otherwise jFj P x2S jF \ E2x j þ jF \ Mj P tðm  1Þ þ k P kðm  1Þ þ k ¼ mk, a contradiction. If t < k ¼ kðG1 Þ, then t 6 dðG1 Þ  1 and dðG1 Þ P 3 because t P 2. Every vertex of S has at least dðG1 Þ  ðt  1Þ neighbors in VðG1 Þ n S, so jEG1 ðSÞj P tðdðG1 Þ  ðt  1ÞÞ ¼ t2 þ ðdðG1 Þ þ 1Þt P 2dðG1 Þ  2 with the same reason as (2). Since the component G02x0  H in G  F, we conclude the following contradiction:

jFj P

X

jF \ E2x j þ jF \ Mj P

x2S

X ðm  1Þ þ 2dðG1 Þ  2 P tðm  1Þ þ 2k  2 P 2ðm  1Þ þ 2k  2 ¼ 2k þ 2m  4: x2S

Since all possible cases lead to a contradiction, k0 ðG1 G2 Þ P minfnðm  1Þ; mk; 2k þ 2m  4g, and the proof is complete. h 4. k0 -optimality of G1 G2 In this section we present some sufficient conditions for G1 G2 to be k0 -optimal. Theorem 4.1. If Gi is a di -regular maximally edge-connected triangle-free graph for i ¼ 1; 2, then k0 ðG1 G2 Þ is k0 -optimal. Proof. Denote G ¼ G1 G2 . By Theorem 3.1, k0 ðGÞ 6 nðGÞ ¼ 2d1 þ 2d2  2. In the following, we show the equality holds. Take e ¼ xx0 2 E1 . We have N G1 ðxÞ [ N G1 ðx0 Þ # V 1 and N G1 ðxÞ \ N G1 ðx0 Þ ¼ ; since G1 is triangle-free. Therefore,

m1 ¼ jV 1 j P jNG1 ðxÞ [ NG1 ðx0 Þj ¼ jNG1 ðxÞj þ jNG1 ðx0 Þj P 2d1 : Similarly, we have m2 P 2d2 . Note that 2d1 þ 2d2  2 6 m1 d2 . In fact, when d2 ¼ 1, 2d1 þ 2d2  2 ¼ 2d1 6 m1 ¼ m1 d2 . When d2 P 2, noting that d1 6 m1  1, we have 2d1 þ 2d2  2 ¼ 2ðd1  1Þ þ 2d2 6 2ðm1  2Þ þ 2d2 6 d2 ðm1  2Þ þ 2d2 ¼ m1 d2 . Similarly, we have 2d1 þ 2d2  2 6 m2 d1 . Suppose to the contrary that k0 ðGÞ < 2d1 þ 2d2  2. Let F be a minimum super edge-cut of G. Since jFj ¼ k0 ðGÞ < 2d1 þ 2d2  2 6 m1 d2 ¼ m1 k2 , there exists some x0 2 V 1 such that G02x0 is connected. To obtain a contradiction, we only need to show that any vertex u of G02x is connected to G02x0 in G  F for every x–x0 . First we show the following claim. Claim. If vertex u is adjacent to another vertex

v 2 V 2x in G  F, then u is connected to G02x

0

in G  F.

Since there are at least d1 edge-disjoint paths between x and x0 in G1 , there are at least 2d1 edge-disjoint paths between fu; v g and V 2x0 in G. If v is connected to G02x0 in G  F, then we are done. Otherwise, F contains at least one edge of each of these paths. Since G2 contains no triangles, jN G2x ðfu; v gÞj ¼ 2d2  2. Thus, there exists at least one vertex u1 2 N G2x ðfu; v gÞ such that uu1 R F (or v u1 R F) and that there is a path from u1 to G02x0 in G  F, otherwise jFj P 2d1 þ 2d2  2, a contradiction. Thus, u can be connected to G02x0 via vertex u1 . By the claim, it is sufficient for us to discuss the case that vertex u is an isolated vertex of G02x in G  F. Since F is a super edge-cut, whose deletion from G does not isolate a vertex, there exists some vertex v 0 2 V 2x0 such that uv 0 R F. If v 0 is not isolated in G02x0 , then v 0 is connected to G02x0 by claim, which means u is connected to G02x0 in G  F. If v 0 is also isolated in G02x0 , then jF \ E2x j P d2 and jF \ E2x0 j P d2 . Because G1 is triangle-free, jN G1 ðfx; x0 gÞj ¼ 2d1  2. There must exist at least one vertex x 2 N G1 ðfx; x0 gÞ such that uu01 R F (or v 0 u01 R F) and u01 is not isolated in G02x , otherwise jFj P 2d2 þ 2d1  2, u01 2 N G2x ðfu; v 0 gÞð a contradiction. Hence, u01 is connected to G02x0 by claim, which implies that u is connected to G02x0 . In a word, the vertex u is always connected to G02x0 in G  F. The contradiction means jFj P 2d1 þ 2d2  2 ¼ nðGÞ. So, the theorem holds. h Topologies of many interconnection networks can be viewed as G1  G2 for some regular graphs G1 and G2 , such as the hypercube Q n , the twisted cube TQ n , the cross cube CQ n , the Möbius cube MQ n and the locally twisted cube LTQ n . Chen et al. [7] have proved that each of these networks is super edge-connected. The n-dimensional toroidal mesh Cðd1 ; d2 ; . . . ; dn Þ [25] can be expressed as the Cartesian product C d1  C d2      C dn , where C di is a cycle of length di for i ¼ 1; 2; . . . ; n. Applying Theorem 4.1, we immediately obtain the k0 -optimality of them. Corollary 4.1. The hypercube Q n , the twisted cube TQ n , the cross cube CQ n , the Möbius cube MQ n and the locally twisted cube LTQ n are all k0 -optimal, that is, the super edge-connectivity are all equal 2n  2 for n P 3, and thus they are all super edgeconnected. Corollary 4.2 [29]. Let Cðd1 ; d2 ; . . . ; dn Þ be the n-dimensional toroidal mesh. Then Cðd1 ; d2 ; . . . ; dn ÞÞ is k0 -optimal, and thus is super edge-connected if di P 4 for each i ¼ 1; 2; . . . ; n. Lemma 4.1 [12]. If G is a k0 -optimal graph, then kðGÞ ¼ dðGÞ. Lemma 4.2. Suppose G is a k0 -graph. Let F be an edge-cut of G such that G  F contains a component H which contains at least two vertices. If G  VðHÞ contains a component with at least two vertices, then jFj P k0 ðGÞ.

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

305

Proof. Let H0 be a component of G  VðHÞ with jVðH0 Þj P 2. Since G is connected, all the components of G  VðHÞ different from H0 , if any, are connected to H and not connected to H0 . So G  VðH0 Þ is connected and jVðG  VðH0 ÞÞj P jVðHÞj P 2, which implies that EG ðVðH0 ÞÞ is a super edge-cut of G. Hence we conclude that jFj P jEG ðVðHÞÞj P jEG ðVðH0 ÞÞj P k0 . h With the proof of Theorem 4.1 in [24], we obtain the super edge-connectivity of product of two k0 -optimal graphs. Theorem 4.2. If G1 and G2 are both k0 -optimal and G2 is d2 -regular, then

minfm1 d2 ; m2 dðG1 Þ; nðG1 G2 Þg 6 k0 ðG1 G2 Þ 6 minfm2 dðG1 Þ; nðG1 G2 Þg: Proof. Since Gi is k0 -optimal, Gi is a k0 -graph and thus mi P 4 for i ¼ 1; 2. Denote dðGi Þ ¼ di , kðGi Þ ¼ ki , nðGi Þ ¼ ni , k0 ðGi Þ ¼ k0i for i ¼ 1; 2 and G ¼ G1 G2 . Due to Lemma 4.1, k1 ¼ d1 and k2 ¼ d2 . Noting that G2 is d2 -regular, we have nðGÞ ¼ minfn1 þ 2d2 ; n2 þ 2d1 g. By Theorem 3.1, we obtain the upper bound

k0 ðGÞ 6 minfm2 d1 ; nðGÞg: Assume to the contrary that k0 ðGÞ < minfm1 d2 ; m2 d1 ; nðGÞg. Let F be a minimum super edge-cut of G. Since jFj < m1 d2 ¼ m1 k2 , there exists some x0 2 V 1 such that G02x0 is connected. We will show that any vertex u of G02x is connected to G02x0 in G  F to deduce a contradiction, where x0 –x. By Menger theorem, there are at least m2 k1 ¼ m2 d1 edge-disjoint paths between G2x and G2x0 in G. Since jFj < m2 d1 , there is at least one path between G02x and G02x0 in G  F. If G02x is connected in G  F, we obtain that u is connected to G02x0 in G  F. Now suppose G02x is disconnected in G  F. There are two cases to consider: Case 1. Vertex u is not isolated in G02x . Denote the component of G02x contains u by H. Consider the following two subcases. Subcase 1.1. G  VðHÞ contains a component with at least two vertices. By Lemma 4.2, jF \ E2x j P k02 ¼ n2 . Because there are at least jVðHÞjk1 edge-disjoint paths connecting H with G2x0 in G, the vertex u is connected to G02x0 in G  F. Otherwise, we obtain the following contradiction

jFj P jF \ E2x j þ jVðHÞjk1 P n2 þ 2d1 P nðGÞ: Subcase 1.2. G  VðHÞ contains only isolated vertices. Then jF \ E2x j P jEG2x ðVðHÞÞj P ðm2  jVðHÞjÞd2 . Obviously, d2 6 m2  1 and n2 ¼ 2d2  2. We claim that vertex u is connected to G02x0 in G  F. Otherwise,

jFj P ðm2  jVðHÞjÞd2 þ jVðHÞjk1 ¼ d2 þ ðm2  jVðHÞj  1Þd2 þ ðjVðHÞj  2Þd1 þ 2d1 P d2 þ ðm2  jVðHÞj  1Þ þ jVðHÞj  2 þ 2d1 ¼ d2 þ ðm2  3Þ þ 2d1 P d2 þ d2  2 þ 2d1 ¼ n2 þ 2d1 P nðGÞ; a contradiction. Case 2. Vertex u is isolated in G02x . Because F is a super edge-cut, vertex u must be adjacent to another vertex in G  F, which x 2 V 1 jVðHÞ \ V 2x –;g. Clearly, is in a copy of G2 different from G2x . Let H be the component of G  F containing u. Denote S ¼ f jVðHÞj P jSj P 2. If VðHÞ \ V 2x0 –;, then vertex u is connected to G02x0 in G  F. In the following we assume VðHÞ \ V 2x0 ¼ ;. If there exists x0 2 S such that G02x0 is connected, then G02x0 is connected to G02x0 in G  F because jFj < m2 d1 ¼ m2 k1 . Thus, the vertex u is connected to G02x0 in G  F. Next we consider the case that G02x0 is disconnected for any x0 2 S. Then jF \ E2x0 j P k2 ¼ d2 for x0 2 S. If there exists a vertex v 2 VðHÞ \ V 2x0 such that v is not an isolated vertex G02x0 , then v is connected to G02x0 in G  F by Case 1. Thus, the vertex u is connected to G02x0 via vertex v in G  F. The remanent case is that every vertex v of H is isolated in the corresponding copy of G2 that contains v. We distinguish the following two subcases. Subcase 2.1. G1  S contains a component with at least two vertices of G1 . By Lemma 4.2, jEG1 ðSÞj P k01 ¼ n1 . The vertex u must be connected to G02x0 , otherwise we obtain the following contradiction:

jFj P n1 þ jVðHÞjd2 P n1 þ jSjd2 P n1 þ 2d2 P nðGÞ: Subcase 2.2. G1  S contains only isolated vertices. Then jEG1 ðSÞj P ðm1  jSjÞd1 . Let D1 be the maximum degree of G1 . Obviously, D1 6 m1  1 and n1 6 D1 þ d1  2. Then, the vertex u is connected to G02x0 in G  F. Otherwise,

jFj P ðm1  jSjÞd1 þ jVðHÞjd2 P ðm1  jSjÞd1 þ jSjd2 ¼ d1 þ ðm1  jSj  1Þd1 þ ðjSj  2Þd2 þ 2d2 P d1 þ ðm1  jSj  1Þ þ jSj  2 þ 2d2 ¼ d1 þ ðm1  3Þ þ 2d2 P d1 þ D1  2 þ 2d2 P n1 þ 2d2 P nðGÞ; a contradiction. Since all possible cases lead to a contradiction, we obtain that jFj P minfm1 d2 ; m2 d1 ; nðGÞg and the proof is complete. h

306

M. Lü et al. / Applied Mathematics and Computation 207 (2009) 300–306

Corollary 4.3. Let Gi be a k0 -optimal graph with order mi P nðGi Þ þ 2, where i ¼ 1; 2. Suppose G2 is a regular graph. Then G1 G2 is k0 -optimal. Proof. Since

m1 P nðG1 Þ þ 2, we can derive that

m1 dðG2 Þ P ðnðG1 Þ þ 2ÞdðG2 Þ ¼ nðG1 ÞdðG2 Þ þ 2dðG2 Þ P nðG1 Þ þ 2dðG2 Þ: Similarly, we have

m2 dðG1 Þ P nðG2 Þ þ 2dðG1 Þ. By Theorem 4.2, the corollary is obtained.

h

Corollary 4.4. If Gi is a di -regular k0 -optimal graph with di P 2 for i ¼ 1; 2, then G1 G2 is k0 -optimal. Proof. Since

mi P di þ 1, we have

m1 d2 P ðd1 þ 1Þd2 ¼ ðd1  1Þðd2  2Þ þ 2d1 þ 2d2  2 P 2d1 þ 2d2  2 ¼ nðGÞ: Similarly, we have

m2 d1 P nðGÞ. By Theorem 4.2, the corollary holds.

h

The multiple-ring networks MRðm; nÞ are defined by MRðm; nÞ ¼ K m  C n , m P 2; n P 2, where C n is a cycle with n vertices. The regular networks Rðr; nÞ are defined recursively by Rðr; 1Þ ¼ K r and Rðr; nÞ ¼ Rðr; n  1Þ  Rðr; 1Þ; n P 2. Employing Theorem 4.2 we give the following result immediately. Corollary 4.5. The multiple-ring networks MRðm; nÞ with m P 2; n P 3 except K 2  C 3 and the regular networks Rðr; nÞ with r P 3 are k0 -optimal, and thus super edge-connected. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31]

C. Balbuena, X. Marcote, P. García-Vázquez, On restricted connectivities of permutation graphs, Networks 45 (2005) 113–118. C. Balbuena, P. García-Vázquez, X. Marcote, Reliability of interconnection networks modeled by a product of graphs, Networks 48 (2006) 114–120. C. Balbuena, P. García-Vázquez, X. Marcote, Sufficient conditions for k0 -optimality in graphs with girth g, J. Graph Theory 52 (2006) 73–86. J.C. Bermond, C. Delorme, G. Farhi, Large graphs with given degree and diameter II, J. Combin. Theory, Ser. B 36 (1984) 32–48. J.C. Bermond, C. Delorme, J.J. Quisquater, Grands graphes non dirigés de degré et diamétre fixés, Ann. Discrete Math. 17 (1982) 65–73. G. Chartrand, A graph-theoretic approach to a communications problem, SIAM J. Appl. Math. 14 (1966) 778–781. Y.C. Chen, J.J.M. Tan, L.H. Hsu, S.S. Kao, Super connectivity and super-edge-connectivity for some interconnection networks, Appl. Math. Comput. 140 (2003) 245–254. W.S. Chiue, B.S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput. 102 (1999) 129–137. A.H. Esfahanian, Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput. 38 (1989) 1586–1591. A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. M.A. Fiol, J. Fàbrega, M. Escudero, Short paths and connectivity in graphs and digraphs, Ars Combinatoria 29B (1990) 253–256. A. Hellwig, L. Volkmann, Sufficient conditions for graphs to be k0 -optimal, super-edge-connected, and maximally edge-connected, J. Graph Theory 48 (2005) 228–246. L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math. 8 (1974) 351–354. L. Li, J.M. Xu, On restricted edge-connectivity of vertex-transitive graphs, J. China Univ. Sci. Tech. 34 (2004) 266–272. M. Lü, G.L. Chen, J.M. Xu, On super edge-connectivity of Cartesian product graphs, Networks 49 (2006) 135–157. M. Lü, J.M. Xu, Super connectivity of line graphs and digraphs, Acta Math. Appl. Sin., Eng. Ser. 22 (2006) 43–48. M. Lü, C. Wu, G.L. Chen, C. Lv, On super connectivity of Cartesian product graphs, Networks 52 (2008) 78–87. J.X. Meng, Y.H. Ji, On a kind of restricted edge connectivity of graphs, Discrete Appl. Math. 117 (2002) 183–193. J. Plesn’ık, Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian Math. 30 (1975) 71–93. L. Shang, H. Zhang, Sufficient conditions for graphs to be k0 -optimal and super-k, Networks 49 (2007) 234–242. B.S. Shieh, Super edge- and point-connectivities of the Cartesian product of regular graphs, Networks 40 (2002) 91–96. T. Soneoka, Super edge-connectivity of dense digraphs and graphs, Discrete Appl. Math. 37/38 (1992) 511–523. T. Soneoka, H. Nakada, M. Imase, C. Peyrat, Sufficient conditions for maximally connected dense graphs, Discrete Math. 63 (1987) 53–66. N. Ueffing, L. Volkmann, Restricted edge-connectivity and minimum edge-degree, Ars Combinatoria 66 (2003) 193–203. J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Boston/London, 2001. J.M. Xu, Theory and Application of Graphs, Kluwer Academic Publishers, Dordrecht/Boston/London, 2003. J.M. Xu, M. Lü, On restricted edge-connectivity of regular digraphs, Taiwan J. Math. 9 (2005) 661–670. J.M. Xu, M. Lü, M.J. Ma, A. Hellwig, Super connectivity of line graphs, Inform. Process. Lett. 94 (2005) 191–195. J.M. Xu, K.L. Xu, On restricted edge-connectivity of graphs, Discrete Math. 243 (2002) 291–298. C.S. Yang, J.F. Wang, J.Y. Lee, F.T. Boesch, Graph theoretic reliability analysis for the Boolean n-cube networks, IEEE Trans. Circuits Syst. 35 (1988) 1175– 1179. C.S. Yang, J.F. Wang, J.Y. Lee, F.T. Boesch, The number of spanning trees of the regular networks, Int. J. Comput. Math. 23 (1988) 185–200.