Super restricted edge connected Cartesian product graphs

Super restricted edge connected Cartesian product graphs

Information Processing Letters 109 (2009) 655–659 Contents lists available at ScienceDirect Information Processing Letters www.elsevier.com/locate/i...

157KB Sizes 0 Downloads 11 Views

Information Processing Letters 109 (2009) 655–659

Contents lists available at ScienceDirect

Information Processing Letters www.elsevier.com/locate/ipl

Super restricted edge connected Cartesian product graphs ✩ Juan Liu a,b , Xing Chen a , Jixiang Meng a,∗ a b

College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, PR China College of Maths-physics and Information Sciences, Xinjiang Normal University, Urumqi, Xinjiang 830054, PR China

a r t i c l e

i n f o

a b s t r a c t

Article history: Received 16 December 2008 Received in revised form 23 February 2009 Accepted 24 February 2009 Available online 9 March 2009 Communicated by A.A. Bertossi Keywords: Cartesian product λ -Optimal Super-λ Combinatorial problems

An edge-cut F of a connected graph G is called a restricted edge-cut if G − F contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity λ (G ) of G. A graph G is said to be λ -optimal if λ (G ) = ξ(G ), where ξ(G ) is the minimum edge-degree of G. A graph is said to be super-λ if every minimum restricted edge-cut isolates an edge. This article gives a sufficient condition for Cartesian product graphs to be super-λ . Using this result, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ . © 2009 Elsevier B.V. All rights reserved.

1. Introduction The underlying topology of an interconnection network is usually modeled by a graph in which the vertices and edges represent the nodes and links, respectively. Traditionally, although the edge-connectivity and super edge-connectivity of a graph have extensively been used for measures of the reliability of the network, these parameters fail to compare the reliability of graphs with the same edge-connectivity and super edge-connectivity. For more accurate measures of the reliability, restricted edge-connectivity and super restricted edge-connectivity are proposed in [2,3]. For networks of the same size and edge failure probability, those that have greater restricted edge connectivity and fewer minimum restricted edge cuts are proved to be more reliable under some reasonable conditions. Hence, graphs with maximal restricted edge connectivity (namely λ -optimal graphs) and the fewest mini-

✩ The research is supported by NSFC (No. 10671165), SRFDP (No. 20050755001) and the Key Project of Chinese Ministry of Education (No. 208161). Corresponding author. E-mail addresses: [email protected]o.com.cn (J. Liu), [email protected] (J. Meng).

*

0020-0190/$ – see front matter doi:10.1016/j.ipl.2009.02.025

© 2009 Elsevier B.V.

All rights reserved.

mum restricted edge-cuts (super-λ graphs have these two properties) have higher reliability, which are just the types of graphs we consider in this paper. Throughout this article, a graph G = ( V , E ) always means a finite undirected connected graph without loops and multiple edges, where V = V (G ) is the vertex set and E = E (G ) is the edge set. For a vertex v ∈ V (G ), N ( v ) denotes the set of vertices adjacent to v, d G ( v ) = | N ( v )| is the degree of v in G. For an edge e = uv ∈ E, let ξG (e ) = d(u ) + d( v ) − 2 be the edge-degree of e. We denote the minimum degree of G by δ(G ) and the minimum edge-degree of G by ξ(G ). An edge-cut in graph G is a set S of edges of G such that G − S is disconnected. The edgeconnectivity λ(G ) of a graph is the minimum cardinality of all edge-cuts of G. A graph G is said to be super-edgeconnected, for short super-λ, if every minimum edge-cut of G isolates a single vertex. Obviously, λ(G )  δ(G ), and if G is super-λ, then λ(G ) = δ(G ). An edge-cut F of G is called a restricted edge-cut if G − F contains no isolated vertices. The minimum cardinality of all restricted edge-cut denoted by λ (G ), is called the restricted edge-connectivity of G. Not every graph contains restricted edge-cuts. For example, the complete graph K 3 and the star K 1,m have no restricted edge-cuts. A connected graph G is called λ -connected if λ (G ) exists. Esfahanian and Hakimi [2] showed that each

656

J. Liu et al. / Information Processing Letters 109 (2009) 655–659

connected graph G with | V (G )|  4, except for the star graph, is λ -connected and satisfies λ(G )  λ (G )  ξ(G ). A restricted edge-cut F is called a λ -cut if | F | = λ (G ). Clearly, for any λ -cut F , the graph G − F consists of exactly two components. A λ -connected graph G is called optimally restricted edge-connected, for short λ -optimal, if λ (G ) = ξ(G ). In order to provide more accurate measures for the fault tolerance of systems of interconnection, Li and Li [3] proposed the concept of super-λ . A graph G is said to be super restricted edge-connected (that is, super-λ ) if every λ -cut of G isolates an edge of G. Obviously, every super-λ graph is also λ -optimal. However, the converse is not trues since many λ -optimal graphs are not super-λ . For example, the cycle of length l (l  6) is a counterexample. For more information on super-λ graphs, please refer to [3,7,11,15]. Let G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) be two graphs which have disjoint vertex sets V 1 and V 2 and disjoint edge sets E 1 and E 2 , respectively. The Cartesian product G 1 × G 2 has vertex set V 1 × V 2 , and ((x1 , x2 ), ( y 1 , y 2 )) ∈ E (G 1 × G 2 ) if and only if either (x1 , y 1 ) ∈ E 1 and x2 = y 2 , or x1 = y 1 and (x2 , y 2 ) ∈ E 2 . In 1957, Sabidussi [8] first discussed the connectivity of the Cartesian product of two undirected graphs. In [1,9,12–14], the authors considered the connectivity, super-connectivity and super-edgeconnectivity of Cartesian product graphs, and in [4,12, 13], the authors introduced some results about connectivity and super (arc) connectivity of Cartesian product of digraphs. In [5,6,10], the authors studied the restricted (edge) connectivity of Cartesian product graphs and λ optimal Cartesian product graphs. This article gives a sufficient condition for Cartesian product graphs to be super-λ . Using this results, certain classes of networks which are recursively defined by the Cartesian product can be simply shown to be super-λ , such as, n-dimensional toroidal mesh and n-dimensional Hypercube. The results in this paper improve results in [5]. The way that we prove the main results is similar to the way in [5]. For the graph terminology and notation not defined here we follow [12]. 2. Main results Let G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) be two graphs. For convenience, V 1 and V 2 are labeled as follows: V 1 = {i 1 | i = 1, 2, . . . , n1 } and V 2 = {i 2 | i = 1, 2, . . . , n2 }, where n1 = | V 1 | and n2 = | V 2 |. We use the symbols ni , δi , ξi , λi , λi to denote the order, the minimum degree, the minimum edge-degree, the edge-connectivity and restricted edge-connectivity of graph G i , respectively, for i = 1, 2. For any vertex (i 1 , i 2 ) ∈ V (G 1 × G 2 ), d G 1 ×G 2 (i 1 , i 2 ) = d G 1 (i 1 ) + d G 2 (i 2 ), and if i 1 j 1 ∈ E 1 and i 2 j 2 ∈ E 2 , then

  ξG 1 ×G 2 (i 1 , i 2 )( j 1 , i 2 ) = ξG 1 (i 1 j 1 ) + 2d G 2 (i 2 ),   ξG 1 ×G 2 (i 1 , i 2 )(i 1 , j 2 ) = ξG 2 (i 2 j 2 ) + 2d G 1 (i 1 ), respectively, and consequently,

ξ(G 1 × G 2 ) = min{ξ1 + 2δ2 , ξ2 + 2δ1 }.

For convenience, we define two kinds of subgraphs in the following. It is clear that, for a vertex i 2 ∈ V 2 , the subgraph i i G 12 of G 1 × G 2 has vertex set V 12 = {(i 1 , i 2 ): i 1 ∈ V 1 } and

i i edge set E 12 = {((i 1 , i 2 )( j 1 , i 2 )): i 1 j 1 ∈ E 1 } and G 12 ∼ = G1. i

Similarly, for a vertex i 1 ∈ V 1 , the subgraph G 21 of G 1 × G 2

= {(i 1 , i 2 ): i 2 ∈ V 2 } and edge set E 2i 1 = {((i 1 , i 2 )(i 1 , j 2 )): i 2 j 2 ∈ E 2 } and G 2i 1 ∼ = G 2 . From the above

has vertex set

i V 21

definitions, we know that i

j

i

j

i

j

i

j

(i) G 12 ∩ G 12 = ∅ for i 2 , j 2 ∈ V 2 , i 2 = j 2 ; G 21 ∩ G 21 = ∅ for i 1 , j 1 ∈ V 1 , i 1 = j 1 . (ii) E 12 ∩ E 12 = ∅ for i 2 , j 2 ∈ V 2 , i 2 = j 2 ; E 21 ∩ E 21 = ∅ for i 1 , j 1 ∈ V 1 , i 1 = j 1 . i i (iii) G 12 ∩ G 21 = {(i 1 , i 2 )} for i 1 ∈ V 1 , i 2 ∈ V 2 .



(iv) G 1 × G 2 = (

i2 ∈V 2



i

G 12 ) ∪ (

i1 ∈V 1

i

G 21 ).

For F ⊆ E (G 1 × G 2 ), let G 12 = G 12 − F

i

i

for any i 2 ∈ V 2 ,

i G 21

i G 21

for any i 1 ∈ V 1 .

=

−F

i

i

i

i

Then, it is clear that V (G 12 ) = V 12 , V (G 21 ) = V 21 for any i 1 ∈ V 1 and i 2 ∈ V 2 , G1 × G2 − F =

 

i

G 12





i2 ∈V 2

 

i



G 21 .

i1 ∈V 1 i

Let C = {i 1 ∈ V 1 | G 21 is connected} and D = {i 2 ∈ V 2 | i G 12

i

is connected}. If H is a subgraph of G 12 , define the

symbol ∂

i

G 12

( V ( H )) as [ V ( H ), V ( H )] ∩

i E (G 12 ).

The following lemmas are needed for the proof. Lemma 2.1. (See [5].) If G is λ -optimal graph, then λ(G ) = δ(G ). Lemma 2.2. (See [5].) λ (G 1 × G 2 ) = min{n1 δ2 , n2 δ1 , ξ(G 1 × G 2 )} if G 1 and G 2 are both λ -optimal. Theorem 2.3. Let G 1 and G 2 be both λ -optimal graphs, if n2 δ1 , n1 δ2 > ξ(G 1 × G 2 ), then G 1 × G 2 is super-λ . Proof. Because G i is λ -optimal, G i is λ -graph for i = 1, 2, which implies ni  4 for i = 1, 2. By Lemma 2.2, G 1 × G 2 is λ -optimal. Suppose that G 1 × G 2 is not super-λ . Let F be a λ -cut such that there is no isolated edge in G 1 × G 2 − F . We should show that G 1 × G 2 − F is connected to deduce a contradiction. Since | F | = ξ(G 1 × G 2 ) < n2 δ1 = n2 λ1 , there x

exists some vertex x1 ∈ V 1 such that G 21 is connected. Analogously, there exists some vertex x2 ∈ V 2 such that x

G 12 is connected. That is to say, |C |  1 and | D |  1. It





i

i

is easy to see that ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ) is connected. There are three cases to be considered.



i

1 Case 1. |C | = n1 . Since i 1 ∈C V 2 = V ( G 1 × G 2 ), we have G 1 × G 2 − F is connected.

J. Liu et al. / Information Processing Letters 109 (2009) 655–659 y

Case 2. |C | = n1 − 1. There is only y 1 ∈ V 1 such that G 2 1 is disconnected. To prove that G 1 × G 2 − F is connected, we only need to show that every vertex in V  = {( y 1 , j 2 ) |

  i i j 2 ∈ V 2 \ D } is connected to ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ). To y this end, let ( y 1 , j 2 ) be any vertex in V 2 1 ( j 2 ∈ V 2 \ D ). Note that F is a λ -cut and there is no isolated edge in G 1 × G 2 − F . If ( y 1 , j 2 ) is only contained in components y

of G 2 1 with at most two vertices, then it is adjacent to

  i i some vertex in ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ). In the following, we suppose that ( y 1 , j 2 ) is contained in a component of y

G 2 1 with at least three vertices. Denote this component by H . We only need to consider the case of V ( H ) ⊆ V  , oth-

  i i erwise ( y 1 , j 2 ) is connected to ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ).

There are two subcases to be considered.

Thus, at least one of the above inequations is strict. A contradiction. Therefore, the vertex ( y 1 , j 2 ) is connected to

  ( i 2 ∈ D G 1i 2 ) ∪ ( i 1 ∈C G 2i 1 ). In a word, G 1 × G 2 − F is connected in this case.

Case 3. |C |  n1 − 2. In this case, to prove that G 1 × G 2 − F is connected, we only need to show that every ver-



j

tex of G 21 is connected to ( j1 ∈ V 1 \ C .

i2 ∈ D



i

G 12 ) ∪ (

i 1 ∈C

i

G 21 ) for

j

Suppose that G 21 contains a component with at least two vertices, denoted by H j 1 , which has no vertices in

  j ( i 2 ∈ D G 1i 2 ) ∪ ( i 1 ∈C G 2i 1 ) for j 1 ∈ V 1 \ C . If G 21 − V ( H j 1 ) contains a component with at least two vertices, similar j to Subcase 2.1, we have | F ∩ E 21 |  |∂ j1 ( V ( H j 1 ))|  λ2 . G2

y

Subcase 2.1. G 2 1 − V ( H ) contains a component with y at least two vertices, denoted by H  . Because G 2 1 is y1 connected, all the components of G 2 − V ( H ) different from H  , if any, are connected to H and are not cony y nected to H  . So G 2 1 − V ( H  ) is connected with | V (G 2 1 −   V ( H ))|  | V ( H )|  3, which implies that ∂G y1 ( V ( H )) is

There is at least one vertex in V ( H j 1 ) is connected to

  ( i 2 ∈ D G 1i 2 ) ∪ ( i 1 ∈C G 2i 1 ). Otherwise, we obtain the following contradiction

  | F |  λ2 +  V ( H j 1 )λ1 + λ2  λ2 + 2λ1 + λ2 = ξ2 + 2δ1 + λ2 > ξ(G 1 × G 2 ). 

2

y G21 .

a restricted edge-cut of Hence, we conclude that y | F ∩ E 2 1 |  |∂G y1 ( V ( H ))|  |∂G y1 ( V ( H  ))|  λ2 . There is at 2

657

2



i2 i2 ∈ D G 1 ) ∪  ( i 1 ∈C G 2i 1 ). Otherwise, we obtain the following contradic-

least one vertex in V ( H ) with neighbors in (

So every vertex of H j 1 is connected to (

 ( i 1 ∈C G 2i 1 ).

i2 ∈ D

i

G 12 ) ∪

j

If G 21 − V ( H j 1 ) contains only isolated vertices. Then

|F ∩

j E 21 |

 |∂

j

G 21

( V ( H j 1 ))|  (n2 − | V ( H j 1 )|)δ2 . We claim

tion

that there is at least one vertex in V ( H j 1 ) with neighbors

  | F |  λ2 +  V ( H )δ1  λ2 + 3δ1 = ξ2 + 3δ1

in (



> ξ(G 1 × G 2 ). 

So the vertex ( y 1 , j 2 ) is connected to (

 ( i 1 ∈C G 2i 1 ).

i2 ∈ D

i

G 12 ) ∪

i2 ∈ D

i



G 12 ) ∪ (

i 1 ∈C

i

G 21 ). Otherwise,

     | F |  n2 −  V ( H j 1 ) δ2 +  V ( H j 1 )λ1 + λ2     = δ2 + n2 −  V ( H j 1 ) − 1 δ2    +  V ( H j 1 ) − 2 δ1 + 2δ1 + λ2         δ2 + n2 −  V ( H j ) − 1 +  V ( H j ) − 2 + 2δ1 + λ2 1

 δ2 + 2 − 2 + 2δ1 + λ2

2

be the maximum degree of G 2 . Obviously, 2  n2 − 1 and ξ2  2 + δ2 − 2. We claim that there is at least one ver-

 ξ2 + 2δ1 + λ2

  i i tex in V ( H ) with neighbors in ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ).

Otherwise,

    | F |  n2 −  V ( H ) δ2 +  V ( H )δ1        = δ2 + n2 −  V ( H ) − 1 δ2 +  V ( H ) − 2 δ1 + 2δ1         δ2 + n2 −  V ( H ) − 1 +  V ( H ) − 2 + 2δ1 

1

= δ2 + (n2 − 3) + 2δ1 + λ2

y

Subcase 2.2. G 2 1 − V ( H ) contains only isolated vertices. y Then | F ∩ E 2 1 |  |∂G y1 ( V ( H ))|  (n2 − | V ( H )|)δ2 . Let 2

> ξ(G 1 × G 2 ), a contradiction. Therefore, every vertex of H j 1 is in or con-



i



i

nected to ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ). / D ) is isolated in Suppose that the vertex ( j 1 , j 2 )( j 2 ∈ j

j

= δ2 + (n2 − 3) + 2δ1

G 21 . Then it is not isolated in G 12 , otherwise, it is isolated in G 1 × G 2 − F , contradicting our hypothesis that F is a λ -cut and there is no isolated edge in G 1 × G 2 − F . So the vertex ( j 1 , j 2 ) is contained in a component with at least

 δ2 + 2 − 2 + 2δ1

two vertices of G 12 . We can show that vertex ( j 1 , j 2 ) is

 ξ2 + 2δ1  ξ(G 1 × G 2 ), note that, if G 1 and G 2 are two graphs with δ1 = 1, δ2 = 1, 2 = n2 − 1 and ξ2 = 2 + δ2 − 2, then

ξ2 + 2δ1 = 2 + δ2 − 2 + 2δ1 = n2 = n2 δ1 > ξ(G 1 × G 2 ).

j

  i i connected to ( i 2 ∈ D G 12 ) ∪ ( i 1 ∈C G 21 ) in the same way as above. Since all possible cases lead to a contradiction, we know that there is an isolated edge in G 1 × G 2 − F for any λ -cut F . 2

Corollary 2.4. Let G 1 and G 2 be both regular λ -optimal graphs. Then G 1 × G 2 is λ -optimal, and is super-λ if and only if G 1 ×

658

J. Liu et al. / Information Processing Letters 109 (2009) 655–659

G 2  K ni × C n j (i = j ∈ {1, 2}), where K ni denotes the complete graph with ni vertices and C n j denotes the cycle with n j vertices. Proof. Since G 1 and G 2 are regular λ -optimal graphs, we have n1  4, n2  4, δ1  2, δ2  2, ξ(G 1 × G 2 ) = 2δ1 + 2δ2 − 2, and λ (G 1 × G 2 ) = min{n1 δ2 , n2 δ1 , 2δ1 + 2δ2 − 2}. Thus,

(1)

Analogously, n1 δ2 = (n1 − 2)δ2 + 2δ2  2(δ1 + 1 − 2) + 2δ2

= 2δ1 + 2δ2 − 2. Therefore, by Lemma 2.2, λ (G 1

× G 2 ) = min{n1 δ2 , n2 δ1 , 2δ1 + 2δ2 − 2} = 2δ1 + 2δ2 − 2 = ξ(G 1 × G 2 ), and thus G 1 × G 2 is λ -optimal. Furthermore, equality holds in (1) if and only if δ1 = 2 and n2 = δ2 + 1, if and only if G 1 ∼ = C n1 and G 2 ∼ = K n2 . Analogously, equality holds in (2) if and only if δ2 = 2 and n1 = δ1 + 1 if and only if G 1 ∼ = K n1 and G 2 ∼ = C n2 . Therefore, if G 1 × G 2  K ni × C n j for i = j ∈ {1, 2}, then n1 δ2 , n2 δ1 > 2δ1 + 2δ2 − 2 = ξ(G 1 × G 2 ). By Theorem 2.3, G 1 × G 2 is super-λ . 2 Corollary 2.5. Let C (d1 , d2 , . . . , dn ) be the n-dimensional toroidal mesh. Then C (d1 , d2 , . . . , dn ) is super-λ if di  4 for each i = 1, 2, . . . , n. Lemma 2.6. (See [5].) Let G be a connected graph with n vertices. Then λ ( K 2 × G ) = min{n, 2λ(G )}. Theorem 2.7. Let G be a connected graph with n vertices and n > 2λ(G ). If G is max-λ, then K 2 × G is λ -optimal. If G is super-λ, then K 2 × G is super-λ . Proof. Note that ξ( K 2 × G ) = 2δ(G ). If G is max-λ, then



λ ( K 2 × G ) = min n, 2λ(G ) = 2λ(G ) = 2δ(G ) = ξ( K 2 × G ). Hence K 2 × G is λ -optimal.

If G is super-λ, then λ(G ) = δ(G ), and if G is also λ connected, then λ (G ) > λ(G ). Suppose that K 2 × G is not super-λ . Let F be a λ -cut such that there is no isolated edge in K 2 × G − F . We should show that K 2 × G − F is connected to deduce a contradiction. There exist two components X and X in K 2 × G − F with | X |, | X |  3. There are two cases to be considered. Set V ( K 2 ) = {x1 , x2 }. Case 1. X ∩ G x1 = ∅ and X ∩ G x2 = ∅. If n − 2  | X ∩ G x1 |  2 or n − 2  | X ∩ G x2 |  2, then

| F |  min λ (G ), 2δ(G ) + δ(G ) > 2δ(G ).

If | X ∩ G xi | = 1 and | X ∩ G x j | = n − 1 for i = j ∈ {1, 2}, then

| F |  δ(G ) + δ(G ) + n − 2 > 2δ(G ). A contradiction.

| F | = n > 2λ(G ) = 2δ(G ). If | X | = n − 1, then

| F | = δ(G ) + (n − 1) > δ(G ) + 2λ(G ) − 1

n2 δ1 = (n2 − 2)δ1 + 2δ1  2(δ2 + 1 − 2) + 2δ1

= 2δ1 + 2δ2 − 2.

Case 2. X ∩ G x1 = ∅ or X ∩ G x2 = ∅. Without loss of generality, set X ∩ G x2 = ∅. Then X ⊆ G x1 . If | X | = n, then

 2δ(G ). If n − 2  | X |  δ(G ), then

| F |  min λ (G ), 2δ(G ) + | X | > 2δ(G ). If | X | < δ(G ), then

  | F |  δ(G )| X | − | X | | X | − 1 + | X |     = 2δ(G ) + δ(G ) | X | − 2 − | X | | X | − 2    = 2δ(G ) + δ(G ) − | X | | X | − 2 > 2δ(G ). Since all possible cases lead to a contradiction, we know that there is an isolated edge in K 2 × G − F for any λ -cut F . Therefore, if G is super-λ, then K 2 × G is super-λ . 2 Lemma 2.8. (See [5].) Let Q n be n-dimensional Hypercube. Then λ ( Q n ) = 2n − 2 and, thus, Q n λ -optimal for n  2, and is super-λ for n  3. Corollary 2.9. n-dimensional Hypercube Q n is super-λ except for n = 1, 3. Proof. If n = 1, 3, then Q 1 and Q 3 is not super-λ . If n = 2, then Q 2 is a cycle of length 4, it is easy to see that Q 2 is super-λ . If n  4, then Q n = K 2 × Q n−1 , | V ( Q n )| = 2n and λ( Q n ) = n, Q n−1 is super-λ for n  4 by Lemma 2.8. Thus, Q n is super-λ for n  4. 2 References [1] W.S. Chiue, B.S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. Comput. 102 (1999) 129–137. [2] A.H. Esfahanian, S.L. Hakimi, On computing a conditional edgeconnectivity of a graph, Inform. Process. Lett. 27 (1988) 195– 199. [3] Q. Li, Q. Li, Reliability analysis of circulant graphs, Networks 31 (1998) 61–65. [4] J. Liu, J. Meng, Super-connected and super-arc-connected Cartesian product of digraphs, Inform. Process. Lett. 108 (2008) 90– 93. [5] M. Lü, G.L. Chen, J.M. Xu, On super edge-connectivity of Cartesian product graphs, Networks 49 (2) (2007) 152–157. [6] M. Lü, C. Wu, G.L. Chen, C. Lv, On super connectivity of Cartesian product graphs, Networks 52 (2) (2008) 78–87. [7] J.P. Ou, F.J. Zhang, Super restricted edge connectivity of regular graphs, Graphs Combin. 21 (2005) 459–467. [8] G. Sabidussi, Graphs with given group and given graph theoretical properties, Canadian J. Math. 9 (1957) 515–525. [9] B.S. Shieh, Super edge- and point-connectivities of the Cartesian product of regular graphs, Networks 40 (2) (2002) 91–96.

J. Liu et al. / Information Processing Letters 109 (2009) 655–659

[10] N. Uefng, L. Volkmann, Restricted edge-connectivity and minimum edge-degree, Ars Combin. 66 (2003) 193–203. [11] Y.Q. Wang, Super restricted edge-connectivity of vertex-transitive graphs, Discrete Math. 289 (2004) 199–205. [12] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht, 2001.

659

[13] J.M. Xu, Connectivity of Cartesian product digraphs and fault-tolerant routings of generalized hypercubes, Appl. Math. J. Chinese Univ. B 13 (2) (1998) 179–187. [14] J.M. Xu, C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159–165. [15] L. Shang, H.P. Zhang, Sufficient conditions for graphs to be λ -optimal and super-λ , Networks 49 (3) (2007) 234–242.