Super-connected and super-arc-connected Cartesian product of digraphs

Super-connected and super-arc-connected Cartesian product of digraphs

Information Processing Letters 108 (2008) 90–93 Contents lists available at ScienceDirect Information Processing Letters www.elsevier.com/locate/ipl...

152KB Sizes 0 Downloads 10 Views

Information Processing Letters 108 (2008) 90–93

Contents lists available at ScienceDirect

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

Super-connected and super-arc-connected Cartesian product of digraphs ✩ Juan Liu, Jixiang Meng ∗ College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang 830046, P.R. China

a r t i c l e

i n f o

a b s t r a c t

Article history: Received 7 January 2008 Available online 11 April 2008 Communicated by L. Boasson

We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained: (i) If δ + ( D i ) = δ − ( D i ) = δ( D i ) = κ ( D i ) for i = 1, 2, then D 1 × D 2 is super-κ if and only if −→ −→ −→ −→ −→ −→ D 1 × D 2  D × K n ( D × K n  K 2 × K 2 , K 2 × K 3 ), + − (ii) If δ ( D i ) = δ ( D i ) = δ( D i ) = λ( D i ) for i = 1, 2, then D 1 × D 2 is super-λ if and only if −→ D 1 × D 2  D × Kn ,

Keywords: Cartesian product Super-connected Super-arc-connected Combinatorial problems

−→

where λ( D ) = δ( D ) = 1, K n denotes the complete digraph of order n and n  2. © 2008 Elsevier B.V. All rights reserved.

1. Introduction By a strict digraph D = ( V ( D ), E ( D )), we mean a directed graph without loops and multiple arcs. Let D = ( V , E ) be a strongly connected digraph and let u and v be two distinct vertices of D. The symbol (u , v ) denotes adj an arc from u to v in D (sometimes denoted by u v), path u D v

denotes a directed path from u to v in D. For and F ⊆ V , set









N + ( F ) = v ∈ V \ F : ∃u ∈ F such that (u , v ) ∈ E , N − ( F ) = v ∈ V \ F : ∃u ∈ F such that ( v , u ) ∈ E ,





E + ( F ) = e = (u , v ) ∈ E: u ∈ F , v ∈ V \ F ,





E − ( F ) = e = ( v , u ) ∈ E: u ∈ F , v ∈ V \ F . Set d+ (u ) = | N + (u )| and d− (u ) = | N − (u )| for F = {u }, which are called out-degree and in-degree, respectively. Set δ + ( D ) = min{d+ (u ): u ∈ V }, δ − ( D ) = min{d− (u ): u ∈ V } and δ( D ) = min{δ − ( D ), δ + ( D )}. The arc-connectivity ✩ The research is supported by NSFC (No. 10671165) and SRFDP (No. 20050755001). Corresponding author. E-mail addresses: [email protected] (J. Liu), [email protected] (J. Meng).

*

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

©

2008 Elsevier B.V. All rights reserved.

λ( D ) is the minimum cardinality of all arc-cuts of D. We call a digraph D maximally-arc-connected, or max-λ, for short, if λ( D ) = δ( D ). A digraph D is said to be super-arcconnected, or super-λ for short, if every minimum arc-cut is E + (u ) or E − (u ) for some u ∈ V . Similarly, the vertex-connectivity κ ( D ), or connectivity, for short, is the minimum cardinality of all vertex-cuts of D. We call a digraph D maximally-connected, or max-κ , for short, if κ ( D ) = δ( D ). A digraph D is said to be super-connected, or super-κ , for short, if every minimum vertex-cut of D is N + (u ) or N − (u ) for some u ∈ V . It is hyper-connected, or hyper-κ , for short, if the removal of any minimum vertex-cut results in exactly two strongly connected components one of −→ which is a singleton. K n denotes the complete digraph of order n, n  2. Let D 1 and D 2 be two digraphs which have disjoint vertex sets V 1 and V 2 and disjoint arc sets E 1 and E 2 , respectively. The Cartesian product D = D 1 × D 2 has vertex set V = V 1 × V 2 , and ((x1 , x2 ), ( y 1 , y 2 )) ∈ E ( D 1 × D 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 [4] first discussed the connectivity of the Cartesian product of two undirected graphs. In [2,3,5–8], the authors considered the connectivity, super-connectivity and super-edge-connectivity of Cartesian product graphs. To name a few, Chiue and Shieh [2] studied the super-connected and super-edgeconnected Cartesian product of two regular graphs, and

J. Liu, J. Meng / Information Processing Letters 108 (2008) 90–93

in [6,7,9], the authors introduced some results about connectivity of Cartesian product of digraphs. In this paper we study the super-connected, hyper-connected and superarc-connected Cartesian product of digraphs. In this paper we will consider the digraph D with δ( D ) = δ + ( D ) = δ − ( D ). Notation and definitions not given here can be found in [1] and [6]. 2. Super-connected Cartesian product of digraphs Let D 1 = ( V 1 , E 1 ) and D 2 = ( V 2 , E 2 ) be two digraphs. i i The subdigraph D 12 of D 1 × D 2 has vertex set V 12 = ∼ {(i 1 , i 2 ) | for any i 1 ∈ V 1 , fixed i 2 ∈ V 2 } = V 1 , and arc set i E 12 = {((i 1 , i 2 ), ( j 1 , i 2 )) | (i 1 , j 1 ) ∈ E 1 } ∼ = E 1 . It is clear that i ∼ i D 12 = D 1 . Similarly, the subdigraph D 21 of D 1 × D 2 has ver-

tex set V 21 = {(i 1 , i 2 ) | for any i 2 ∈ V 2 , fixed i 1 ∈ V 1 } ∼ = V 2, i

and arc set E 21 = {((i 1 , i 2 ), (i 1 , j 2 )) | (i 2 , j 2 ) ∈ E 2 } ∼ = E 2 . It is i

clear that that i

i D 21

∼ = D 2 . From the above definitions, we know

j

j

i

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

  ( i 2 ∈ V 2 D 1i 2 ) ∪ ( i 1 ∈ V 1 D 2i 1 ).

For convenience, V 1 and V 2 are labeled as follows: V 1 = {i 1 | i = 1, 2, . . . , n1 } and V 2 = { j 1 | j = 1, 2, . . . , n2 }, where n1 = | V 1 | and n2 = | V 2 |. We use the symbols ni , δi , κi , λi to denote the order, the minimum degree, the connectivity and arc-connectivity of digraph D i , respectively, for i = 1, 2. The following lemma is needed for the proof. Lemma 2.1. (See [9].) For every two nontrivial strongly connected digraph D 1 and D 2 ,





κ ( D 1 × D 2 ) = min n1 κ1 , n2 κ2 , δ1+ + δ2+ , δ1− + δ2− ,   λ( D 1 × D 2 ) = min n1 λ1 , n2 λ2 , δ1+ + δ2+ , δ1− + δ2− .

we consider n  3. Note that κ ( D ) = 1. Let u be a cutvertex of D, u ∈ {1, 2, . . . , n }, let B 1 , B 2 , . . . , B t be t distinct strongly connected components of D − {u }, and there is a B i (i ∈ {1, 2, . . . , t }) such that N + ( B i ) = ∅. Choose −→D U = {(u , j ) | j = 1, 2, . . . , n}, then D × K n − U has t strongly −→ −→ −→ connected components B 1 × K n , B 2 × K n , . . . , B t × K n , and −→ + −→ N D × K n ( B i × K n ) = ∅. Hence, U is neither the out-neighbor set nor the in-neighbor set of a vertex. −→ −→ −→ −→ On the other hand, if D 1 × D 2 ∼ = K 2 × K 2 or K 2 × K 3 , then it is easy to check that D 1 × D 2 is super-κ . In the fol−→ lowing, we prove that if D 1 × D 2  D × K n where κ ( D ) = δ( D ) = 1 and n  2, then D 1 × D 2 is super-κ . Let U be a minimum vertex-cut set of D 1 × D 2 . For convenience, let j j j i i i D 12 = D 12 − (U ∩ V 12 ) for i 2 ∈ V 2 and D 21 = D 21 − (U ∩ V 21 ) for j 1 ∈ V 1 . Suppose that U is neither the out-neighbor set nor the in-neighbor set of a vertex. We want to show that for a pair of vertices X = (x1 , x2 ) and Y = ( y 1 , y 2 ) in D 1 × D 2 − U there exists one path from X to Y . There are three cases depending on X and Y : Case 1. x1 = y 1 and x2 = y 2 , say X = (x1 , x2 ) and Y = (x1 , y 2 ). If D 2x1 is strongly connected, then one path from x X to Y must exist. If D 21 is not strongly connected, then y2 x2 |U ∩ ( V 1 ∪ V 1 )|  κ1 since |U | = κ1 + κ2 and |U ∩ V 2x1 |  κ2 , thus at most one of the digraphs D 1x2 and D 1y2 could not be strongly connected. There are four cases to be considered: Subcase 1.1. δi = κi  2 for i = 1, 2. y x Since at most one of the digraphs D 12 and D 1 2 could not be strongly connected, we consider the following two subcases. Subcase strongly Without strongly tex) and x

Theorem 2.2. Let D 1 and D 2 be two strict strongly connected digraphs and let δi+ = δi− = δi for i = 1, 2. If δi = κi , then D 1 × −→ −→ D 2 is super-κ if and only if D 1 × D 2  D × K n ( D × K n  −→ −→ −→ −→ K 2 × K 2 , K 2 × K 3 ), where κ ( D ) = δ( D ) = 1, n  2. Proof. By Lemma 2.1, note that κ ( D 1 × D 2 ) = κ1 + κ2 = −→ δ1 + δ2 = δ( D 1 × D 2 ). Suppose that D 1 × D 2 ∼ = D × Kn −→ −→ −→ −→ −→ ( D × K n  K 2 × K 2 , K 2 × K 3 , κ ( D ) = δ( D ) = 1, n  2), we will prove that D 1 × D 2 is not super-κ . We label the ver−→ −→ tices of D × K n and write V ( D ) × V ( K n ) = {(i , j ) | i = −→ 1, 2, . . . , n and j = 1, 2, . . . , n}. Note that κ ( D × K n ) = n. −→ We want to find a minimum vertex-cut set U of D × K n such that U is neither the out-neighbor set nor the inneighbor set of a vertex. First, we consider n = 2. Thus, −→ −→ −→ −→ −→ −→ −→ −→ D × K n = K 2 × K n . Since D × K n  K 2 × K 2 and K 2 × K 3 , we consider n  4. Choose U = {(1, 1), (1, 2), (2, 3), . . . , (2, n)}, −→ −→ then K 2 × K n − U is not strongly connected and each component has at least two vertices. Hence, U is neither the out-neighbor set nor the in-neighbor set of a vertex. Next,

91

y

x

1.1.1. One of the digraphs D 12 and D 1 2 is not connected, and the other is strongly connected. x loss of generality, we assume that D 12 is not x2 connected (including that D 1 is an isolated very D 1 2 is strongly connected. Then, x

U ⊂ V 12 ∪ V 21 .

(1)

Since U is neither the out-neighbor set nor the in-neighbor set of a vertex, there exist i 1 ∈ V 1 or j 2 ∈ V 2 such that there is an arc from X to (i 1 , x2 ) or (x1 , j 2 ). By (1) and κ2  2, we know that D t21 is strongly connected for all t 1 = x1 , t 1 ∈ V 1 . Hence, one of the following paths will exist: adj

path

path

i D 21

D12

path

path

path

j

D 21

t

D12

X = (x1 , x2 ) ——(i 1 , x2 ) ———(i 1 , y 2 ) ———(x1 , y 2 ) = Y y

(2)

or adj

X = (x1 , x2 ) ——(x1 , j 2 ) ———(t 1 , j 2 ) ———(t 1 , y 2 ) ———(x1 , y 2 ) D 12

y

= Y.

(3) x

y

Subcase 1.1.2. Both D 12 and D 1 2 are strongly connected. i

Note that if one of the digraphs D 21 for i = 1, 2, . . . , n1 , i 1 = x1 is not strongly connected, then there exists t 1 ∈ V 1

92

J. Liu, J. Meng / Information Processing Letters 108 (2008) 90–93 t

t

such that D 21 = D 21 since |U | − 2κ2  κ1 − 2  n1 − 3. In this case, it is clear that we have one path from X to Y : path

path

path

x

D 21

t

D12

X = (x1 , x2 ) ———(t 1 , x2 ) ———(t 1 , y 2 ) ———(x1 , y 2 ) = Y . D 12

(4)

y

i

Thus, we only need to consider the case that D 21 is strongly connected for all i 1 = x1 , i 1 ∈ V 1 . There are two possibilities: If there exists t 1 such that both the vertices (t 1 , x2 ) and (t 1 , y 2 ) are not in U , then we have one path from X to Y as (4). Otherwise, one of the vertices (i 1 , x2 ) and (i 1 , y 2 ) is in U and the other is not in U for all i 1 = x1 since κ1  n1 − 1. In this case, we have x

y

x

j

U ⊂ V 21 ∪ V 12 ∪ V 1 2 . Consequently, D 12 is strongly connected for all j 2 ∈ V 2 and a path from X to Y exists as follows: X = (x1 , x2 ) ———(i 1 , x2 ) ———(i 1 , j 2 ) ———(i 1 , j 2 ) path

path

path

i

D 12

x

D 12

j

D 21

———(i 1 , y 2 ) ———(x1 , y 2 ) = Y , path

path

i D 21

D12

y

for some j 2 ∈ V 2 , j 2 = x2 , y 2 , and i 1 , i 1 ∈ V 1 , x1 = i 1 , i 1 . −→

Subcase 1.2. κi = δi = 1 and D i  K 2 for i = 1, 2. x We known that n1 , n2  3 in this case. Since D 21 is not x1 strongly connected, |U | = 2, |U ∩ V 2 |  1, we have |U ∩ y ( V 1x2 ∪ V 1 2 )|  κ1 = 1. Since |U | = 2 < n1 , there exists t 1 = t

y

x

Subcase 1.4.2. Both D 12 and D 1 2 are strongly connected. t

t

There exists t 1 ∈ V 1 such that D 21 = D 21 since |U | = 1 + κ1 < n1 . Hence, we have one path from X to Y as (4). Case 2. x2 = y 2 and x1 = y 1 . This case is analogous to Case 1. Case 3. x2 = y 2 and x1 = y 1 .There are three subcases to be considered: Subcase 3.1. There exists j 2 ∈ V 2 such that both the vertices (x1 , j 2 ) and ( y 1 , j 2 ) are not in U . By Cases 1 and 2, we obtain one path form X to Y : path

path

path

X = (x1 , x2 ) —— (x1 , j 2 ) —— ( y 1 , j 2 ) —— ( y 1 , y 2 ) = Y .

(5)

Subcase 3.2. There exists i 1 ∈ V 1 such that both the vertices (i 1 , x2 ) and (i 1 , y 2 ) are not in U . Similarly, we have one path form X to Y : path

y

y

x

Subcase 1.2.2. |U ∩ ( V 12 ∪ V 1 2 )| = 0. We have one path from X to Y as (4). Subcase 1.3. κ1 = δ1 = 1 and 2  κ2 = δ2  n2 − 2. x x Since D 21 is not strongly connected, |U ∩ V 21 | 

κ2 ,

|U | = 1 + κ2 and κ2  2, thus, the digraphs D k21 are strongly x connected for all k1 ∈ V 1 , k1 = x1 . Clearly, |U ∩ ( V 12 ∪ y2 V 1 )|  κ1 = 1. We consider the following two subcases: y

Subcase 1.3.1. |U ∩ ( V 12 ∪ V 1 2 )| = 1. Without loss of genx erality, we assume that |U ∩ V 12 | = 1, then (1) holds. The following proof is analogous to Subcase 1.1.1. x

Thus, similar to Subcase 1.1.1, one of the paths as (2) and (3) will exist.

y

Subcase 1.3.2. |U ∩ ( V 12 ∪ V 1 2 )| = 0. Since n1  2, there t D 21

exists t 1 ∈ V 1 and t 1 = x1 such that is strongly connected. We have one path from X to Y as (4).

Subcase 1.4. 2  κ1 = δ1  n1 − 2 and κ2 = δ2 = 1. y x Since at most one of the digraphs D 12 and D 1 2 could not be strongly connected, we consider the following two subcases. x

path

path

X = (x1 , x2 ) —— (i 1 , x2 ) —— (i 1 , y 2 ) —— ( y 1 , y 2 ) = Y .

Subcase 1.2.1. |U ∩ ( V 12 ∪ V 1 2 )| = 1. Without loss of generx ality, we assume that |U ∩ V 12 | = 1, then (1) holds. Similar to Subcase 1.1.1, one of the paths as (2) and (3) will exist.

x

|U | = 1 + κ1 < n1 , there exists t 1 ∈ V 1 such that D t21 = D t21 .

t

x1 , t 1 ∈ V 1 such that D 21 = D 21 . We consider the following two subcases: x

x

Without loss of generality, we assume that D 12 is not x strongly connected (including that D 12 is an isolated very2 tex) and D 1 is strongly connected. Then (1) holds. Since

y

Subcase 1.4.1. One of the digraphs D 12 and D 1 2 is not strongly connected, and the other is strongly connected.

(6)

Note that if κ1 = 1 or κ2 = 1, then |U | = 1 + κ1 < n1 or |U | = 1 + κ2 < n2 , there exists i 1 ∈ V 1 or j 2 ∈ V 2 such that j j i i D 21 = D 21 or D 12 = D 12 . Thus we have one path from X to Y as (5) or (6). Therefore, we will consider that κi  2 in the following for i = 1, 2. Subcase 3.3. For any i 1 ∈ V 1 , j 2 ∈ V 2 , one of the vertices (i 1 , x2 ) and (i 1 , y 2 ) is in U and the other is not in U , and one of the vertices (x1 , j 2 ) and ( y 1 , j 2 ) is in U and the other is not in U , since |U | = κ1 + κ2  n1 + n2 − 2. In this case, we have x

y

x

y

U ⊂ V 21 ∪ V 2 1 ∪ V 12 ∪ V 1 2 .

(7)

Since U is neither the out-neighbor set nor the in-neighbor set of some vertex, there are four possibilities to be considered: Subcase 3.3.1. There are arcs from X to (i 1 , x2 ) and from (i 1 , y 2 ) to Y for some i 1 , i 1 ∈ V 1 . Since n2  3, there exists j 2 ∈ V 2 such that j 2 = x2 , y 2 , By (7) and Cases 1 and 2, we have one path from X to Y : X = (x1 , x2 ) —— (i 1 , x2 ) —— (i 1 , j 2 ) —— (i 1 , j 2 ) adj

path

path

—— (i 1 , y 2 ) —— ( y 1 , y 2 ) = Y .

path

adj

Subcase 3.3.2. There are arcs from X to (x1 , j 2 ) and from ( y 1 , j 2 ) to Y for some j 2 , j 2 ∈ V 2 . This case is analogous to Subcase 3.3.1.

J. Liu, J. Meng / Information Processing Letters 108 (2008) 90–93

Subcase 3.3.3. There are arcs from X to (i 1 , x2 ) and from ( y 1 , j 2 ) to Y for some i 1 ∈ V 1 , j 2 ∈ V 2 . By (7) and Cases 1 and 2, we have one path from X to Y : adj

path

path

adj

X = (x1 , x2 ) —— (i 1 , x2 ) —— (i 1 , j 2 ) —— ( y 1 , j 2 ) —— ( y 1 , y 2 )

= Y. Subcase 3.3.4. There are arcs from X to (x1 , j 2 ) and from (i 1 , y 2 ) to Y for some j 2 ∈ V 2 , i 1 ∈ V 1 . This case is analogous to Subcase 3.3.3. Thus, D 1 × D 2 − U is strongly connected in all possible cases. This is a contradiction. Hence, U is the out-neighbor set or in-neighbor set of a vertex. 2 Theorem 2.3. Assume κi  2 or κ1 = 1 and 2  κ2  n2 − 2 for i = 1, 2. If D 1 and D 2 are max-κ , then D 1 × D 2 is hyper-κ . Proof. By Theorem 2.2, we know that D 1 × D 2 is super-κ . Let U be a minimum vertex-cut of D 1 × D 2 , without loss of generality, assume that U is the out-neighbor set of some x x vertex, say (x1 , x2 ) ∈ V ( D 1 × D 2 ). Note that U ⊆ D 12 ∪ D 21





j

i

and ( j 2 ∈ V 2 j 2 =x2 D 12 ) ∪ ( i 1 ∈ V 1 i 1 =x1 D 21 ) is a spanning subdigraph of D 1 × D 2 − U − {(x1 , x2 )}, thus, in order to prove that D 1 × D 2 is hyper-κ , we just need to prove that   j ( j 2 ∈ V 2 j 2 =x2 D 12 )∪( i 1 ∈ V 1 i 1 =x1 D 2i 1 ) is strongly connected. Two cases are considered: j

i

Case 1. κi  2 for i = 1, 2. Since D 21 and D 12 are strongly connected for all i 1 ∈ V 1 , j 2 ∈ V 2 , i 1 = x1 , j 2 = x2 , hence,

  j ( j 2 ∈ V 2 , j 2 =x2 D 12 ) ∪ ( i 1 ∈ V 1 ,i 1 =x1 D 2i 1 ) is strongly con-

nected.

t

t

then V 12 − (x1 , t 2 ) ⊆ 1+

Proof. Note that λ( D 1 × D 2 ) = λ1 + λ2 = δ1 + δ2 = −→ δ( D 1 × D 2 ). Suppose that D 1 × D 2 ∼ = D × K n where λ( D ) = δ( D ) = 1, n  2, we will prove that D 1 × D 2 is −→ not super-λ. We label the vertex set of D × K n and write −→ V ( D ) × V ( K n ) = {(i , j ) | i = 1, 2, . . . , n and j = 1, 2, . . . , n}. −→ Note that λ( D × K n ) = n. We want to find a minimum −→ arc-cut set U of D × K n such that U is neither the outarc set nor the in-arc set of a vertex. Since λ( D ) = 1, there is a cut-arc e in D such that D − {e } has t distinct strongly connected components B 1 , B 2 , . . . , B t and there is a B i (1  i  t ) such that E + ∅. Note that D j ∼ =D D ( B i ) =−→ −→ for any fixed j ∈ V ( K n ) and λ( D × K n ) = n, n  2. Let e j denote the cut-arc in D j such that D j − {e j } has t disj j j tinct strongly connected components B 1 , B 2 , . . . , B t and

there is a B i (i ∈ {1, 2, . . . , t }) such that E + j ( B i ) = ∅. j



j

D

−→

Choose U = j ∈ V (−K→n ) {e }; then, we have |U | = | V ( K n )| = n −→ and D × K n − U has t strongly connected components −→ −→ −→ −→ −→ B 1 × K n , B 2 × K n , . . . , B t × K n , and E + D × K n ( B i × K n ) = ∅. Hence U is neither the out-arc set nor the in-arc set of a vertex. −→ On the other hand, if D 1 × D 2  D × K n where κ ( D ) = δ( D ) = 1, n  2. The following proof follows the same outline as in Theorem 2.2 with the changes between κ and λ, V and E, and vertex and arc, except for Case 3. We spell it out in detail as follows and complete the proof: j

Case 3. x1 = y 1 and x2 = y 2 . By Cases 1 and 2, we have one path from X to Y : path

path

X = (x1 , x2 ) —— (x1 , y 2 ) —— ( y 1 , y 2 ) = Y .

2

References

Case 2. κ1 = 1 and 2  κ2  n2 − 2. Note that D 12 ∩ x D 21 = {(x1 , t 2 )} for any t 2 ∈ V 2 \ {x2 }. If (x1 , t 2 ) ∈ U , t D 12

93



i 1 ∈ V 1 ,i 1 =x1

i

V 21 ; if (x1 , t 2 ) ∈ / U , then

is strongly connected. Since 2  κ2  n2 − 2, |U | = κ2 < n2 , there exists s2 ∈ V 2 such that D 1s2 = D 1s2 .



j



Hence, ( j 2 ∈ V 2 , j 2 =x2 D 12 ) ∪ ( connected. 2

i 1 ∈ V 1 ,i 1 =x1

i

D 21 ) is strongly

3. Super-arc-connected Cartesian product of digraphs Theorem 3.1. Let D 1 and D 2 be two strict strongly connected digraphs and let δi+ = δi− = δi for i = 1, 2. If δi = λi , then D 1 × −→ D 2 is super-λ if and only if D 1 × D 2  D × K n where λ( D ) = δ( D ) = 1, n  2.

[1] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Athenaum Press Ltd., 2001. [2] W.S. Chiue, B.S. Shieh, On connectivity of the Cartesian product of two graphs, Appl. Math. and Comput. 102 (1999) 129–137. [3] M. Lü, G.L. Chen, J.M. Xu, On super edge-connectivity of Cartesian product graphs, Networks 49 (2) (2007) 152–157. [4] G. Sabidussi, Graphs with given group and given graph theoretical properties, Canadian J. of Math. 9 (1957) 515–525. [5] B.S. Shieh, Super edge- and point-connectivities of the Cartesian product of regular graphs, Networks 40 (2) (2002) 91–96. [6] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht, 2001. [7] J.M. Xu, Connectivity of Cartesian product digraphs and faulttolerant routings of generalized hypercubes, Appl. Math. J. Chinese Univ. 13B (2) (1998) 179–187. [8] J.M. Xu, C. Yang, Connectivity of Cartesian product graphs, Discrete Math. 306 (2006) 159–165. [9] C. Yang, J.M. Xu, Reliability of interconnection networks modeled by Cartesian product digraphs, Networks, in press.