# 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...

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

λ( 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  ﬁrst 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  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 deﬁnitions not given here can be found in  and . 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 , ﬁxed 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 , ﬁxed 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 deﬁnitions, 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 .) 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 ﬁnd 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)

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

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

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 ﬁnd 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 ﬁxed 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.

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