# On Arc Connectivity of Direct-Product Digraphs

Authors: Tiedan Zhu; Jianping Ou
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

Four natural orientations of the direct product of two digraphs are introduced in this paper. Sufficient and necessary conditions for these orientations to be strongly connected are presented, as well as an explicit expression of the arc connectivity of a class of direct-product digraphs.


---

## Body

## 1. Introduction

Various product operations are employed for constructing larger networks from smaller ones, among which direct-product operation is the most frequently employed one. The direct product of two graphsG1 and G2, denoted by G1×G2, is defined on vertex set V(G1)×V(G2), where two vertices (x1,x2) and (y1,y2) are adjacent to each other in G1×G2 if and only if x1y1∈E(G1) and x2y2∈E(G2). Other names for direct product are tensor product, categorical product, Kronecker product, cardinal product, relational product, and weak direct product [1]. Some basic connectivity properties of direct-product graphs are presented in [2, 3] and elsewhere. Specially, the authors characterize connected product graphs by presenting the following Theorem 1.1 in [1]; an explicit expression of the connectivity of a direct-product graph is presented in [4].Theorem 1.1 (see [1, Theorem  5.29]).
LetG and H be connected nonempty graphs. Then G×H is connected if and only if at least one of them is nonbipartite. Furthermore, if both G and H are bipartite, then G×H has exactly two components.LetD1=(V1,A1) and D2=(V2,A2) be two digraphs. It is naturally to define the vertex set and adjacency relationship between vertices of direct product of digraph as those of undirected graphs. But the orientation is not unique, for every pair of arcs (x1,y1)∈A1 and (x2,y2)∈A2, there are four natural orientations of the two edges (x1,x2)(y1,y2) and (y1,x2)(x1,y2). For clarity and comparison, we depicture the Cartesian product K2→□K2→ and the four orientations of direct-product digraph K2→×K2→ in Figure 1.Figure 1
Orientations of direct-product digraphK2→×K2→.A digraph is strongly connected or disconnected if any vertex is reachable from any other vertex, where a vertexu is said to be reachable form another vertex v if there is a directed path from v to u. The minimum number λ(D) of arcs needed to be removed for destroying the strong connectivity of a digraph is called its arc connectivity. This work characterizes strongly connected direct-product digraphs of the above four orientations. We follow [5] for symbols and terminology not specified in this work.


## 2. Strongly Connected Direct-Product Digraphs

As will be shown in next section, the above four orientations can be transformed by one another to some extent. So we assume in this section thatD1×D2 contains an arc from vertex (x1,x2) to (y1,y2) if and only if arc (x2,y2)∈A(D2), and (x1,y1)∈A(D1) or (y1,x1)∈A(D1).Lemma 2.1.
LetD be a digraph. Then K2→×D is strongly connected if and only if D is nonbipartite and strongly connected.Proof.
Necessity. If D is bipartite, then by Theorem 1.1 the underlying graph of K2→×D is disconnected. This contradiction shows that D is nonbipartite. Let {a,b} be the vertex set of K2→. Since K2→×D is strongly connected, it follows that for any two vertices u,v∈V(D), K2→×D contains a directed walk W1 from (a,u) to (a,v). Let W1=(a,u)(b,v1)(a,v2)⋯(b,vk)(a,v). Then it yields a directed walk uv1v2⋯vkv of D. The necessity follows from this observation.
Sufficiency. Since D is strongly connected, it contains a spanning closed directed walk W=u0v1v2⋯vku0, which corresponds two directed walks W′=(a,u0)(b,v1)(a,v2)⋯(x,u0) and W′′=(b,u0)(a,v1)(b,v2)⋯(y,u0) of K2→×D, where x,y∈{a,b}. It is obvious that W′∪W′′ is a spanning subgraph of V(K2→×D).
Case  1. The length of W=u0v1v2⋯vku0 is odd, say, k=2n.
In this case,W′=(a,u0)(b,v1)(a,v2)⋯(a,v2n)(b,u0) and W′′=(b,u0)(a,v1)(b,v2)⋯(b,v2n)(a,u0). And so W′∪W′′ is a spanning closed directed walk of K2→×D. Hence, K2→×D is strongly connected.
Case  2. The length of W=u0v1v2⋯vku0 is even, say, k=2n+1.
In this case, bothW′=(a,u0)(b,v1)(a,v2)⋯(a,v2n)(a,u0) and W′′=(b,u0)(a,v1)(b,v2)⋯(b,v2n)(b,u0) are closed directed walks. Since D is nonbipartite, it contains an arc joining two vertices of W whose suffixes have same parity. Without loss of generality, let (u0,v2l)∈A(D). This arc corresponds to two arcs ((a,u0),(b,v2l)), ((b,u0),(a,v2l)) of K2→×D. These two arcs make W′ and W′′ reachable from each other. Therefore, K2→×D is strongly connected.Theorem 2.2.
LetD1 and D2 be two digraphs. Then D1×D2 is strongly connected if and only if D2 is strongly connected and D1 or D2 is nonbipartite.Proof.
Sufficiency. If D2 is nonbipartite and strongly connected, by Lemma 2.1, D1×D2 is strongly connected.
IfD2 is strongly connected and bipartite, but D1 is nonbipartite, then D2 contains a spanning closed directed walk W2=u0u1u2⋯uku0. Since D2 is bipartite, it follows that k is odd. Let W1=v0v1v2⋯vi⋯v2m+ivi⋯vsv0 be a spanning closed walk of D1, where C=vi⋯v2m+ivi is an odd cycle. For any vertex vj∈V(W1) and any one of its neighbor vl in W1, Wj′=(vj,u0)(vl,u1)(vj,u2)⋯(vl,uk)(vj,u0)≅W2 and V(D)=∪i=0sV(Wi′). Since vj and vl are adjacent in W1, it follows that l=j+1 or 2m+j. Let
(2.1)W′′=(vj,u0)(vj+1,u1)(vj,u2)⋯(vj+1,uk)(vj,u0),W′′′=(vj,u0)(v2m+j,u1)(vj,u2)⋯(v2m+j,uk)(vj,u0).
The sum of the suffixes of each vertex inW′′ has the same parity as the integer j. Since vj may be any vertex of W1, it follows that the vertices of V(D1)×V(D2) whose suffix sum has same parity induce a strong component (a strongly connected vertex-induced subgraph with as many as possible vertices). Since W′′′ contains vertices with odd suffix sum as well vertices with even suffix sum, it follows that D1×D2 is strongly connected.
Necessity. Since D1×D2 is strongly connected, every two vertices (ui,vj) and (uk,vl) are reachable from each other in D1×D2. It follows that vj and vl are reachable from each other in D2. Hence, D2 is strongly connected. If D2 is strongly connected, but both D1 and D2 are bipartite, then D1×D2 is not strongly connected by Lemma 2.1. The necessity follows from this contradiction.


## 3. Relationship of the Four Orientations

The last three orientations of Figure1 can be defined as follows, respectively.Orientation 2. Let D1=(V1,A1) and D2=(V2,A2) be two digraphs. D1×D2 contains an arc from (x1,x2) to (y1,y2) if and only if (y2,x2)∈A2, and (y1,x1) or (x1,y1)∈A1.Orientation 3. Let D1=(V1,A1) and D2=(V2,A2) be two digraphs. D1×D2 contains an arc from (x1,x2) to (y1,y2) if and only if (x1,y1)∈A1, and (x2,y2) or (y2,x2)∈A2.Orientation 4. Let D1=(V1,A1) and D2=(V2,A2) be two digraphs. D1×D2 has an arc from (x1,x2) to (y1,y2) if and only if (y1,x1)∈A1, and (x2,y2) or (y2,x2)∈A2.The readers are suggested to refer to (2), (3), and (4) of Figure2 for Orientations 2, 3, and 4 respectively. It is not difficult to see that Orientation 2 is the converse of the first orientation in Figure 1. And so, the following Corollary 3.1 follows directly from Theorem 2.2. Similarly, if D2×D1 has Orientation  1 (refer to (2) of Figure 1)  and D1×D2 has Orientation 3 then D2×D1≅D1×D2. From this observation and Corollary 3.1, Corollary 3.2 follows directly.Figure 2
Partition ofV(K2→×D-S).Corollary 3.1.
LetD1×D2 be oriented as Orientation 2. Then it is strongly connected if and only if D2 is strongly connected and D1 or D2 is nonbipartite.Corollary 3.2.
LetD1×D2 be oriented as in Orientations 3 or 4. Then it is strongly connected if and only if D1 is strongly connected and D1 or D2 is nonbipartite.


## 4. Strong Arc Connectivity

LetD be a strongly arc connected digraph and X⊊V(D) be a nonempty vertex set. Denote by (X,V(D)-X) the set of arcs with tail in X and head in V(D)-X, which is called a directed cut of D. If T is a directed cut of strongly connected digraph D, then D-T is connected but is not strongly connected. The size λ(D) of minimum directed cuts of digraph D is called its strong arc connectivity. Let β(D)=min{|S|:S⊂A(D)suchthatD-Sisabipartitegraph}, δ(D)=min{δ+(D),δ-(D)} be the minimum degree of D. For every integer δ(D)≥j≥λ(D), let βj=min{β(C):C be any strongly connected component of D-T and T is an arbitrary directed cut of D of size j}.LetD1×D2 be oriented according to the first orientation of Figure 1. For every arc ((x1,x2),(y1,y2)) of D1×D2, the arc (x2,y2)∈A(D2) is called its projection on D2. The following Lemma 4.1 is immediate, so we omit its proof herein.Lemma 4.1.
If directed graphD is not strongly connected, then it contains two strongly connected components, one of which has no outer neighbors and the other has no inner neighbors.Theorem 4.2.
IfK2→×D is strongly connected, then λ(K2→×D)=min{2λ(D),β(D),min{j+βj:λ(D)≤j≤δ}}.Proof .
By Lemma2.1, Theorem 4.2 is clearly true in the case when D is bipartite, and so we assume in what follows that β(D)≥1 and D is nonbipartite. Let T be a minimum direct cut of D and let F be a minimum arc-set of D such that D-F=(X,Y;E) is a bipartite graph with bipartition X and Y. Then β(D)=|F| and, λ(D)=|T|≥1 by Lemma 2.1.
Claim  1.
λ
(
K
2
→
×
D
)
≤
min
{
2
λ
(
D
)
,
β
(
D
)
,
min
{
j
+
β
j
:
λ
(
D
)
≤
j
≤
δ
}.
LetA(K2→)={(a,b)}. By Theorem 1.1, K2→×(D-F) consists of two components. The vertex sets of these two components are {(a,x):x∈X}∪{(b,y):y∈Y} and {(b,x):x∈X}∪{(a,y):y∈Y}. It is not difficult to see that {((a,x),(b,y)):(x,y)∈F∩A(D[X])}∪{((b,x),(a,y)):(x,y)∈F∩A(D[Y])} is a directed cut of K2→×D, since its removal makes {(b,x):x∈X}∪{(a,y):y∈Y} not reachable from {(a,x):x∈X}∪{(b,y):y∈Y}. And so, λ(K2←×D)≤|F|=β(D).
By Lemma4.1, D-T contains a strongly connected component D1 that has no outer neighbors. By the minimality of T, we have (D1,D1¯)=T. Obviously, {((a,x),(b,y)):(x,y)∈T}∪{((a,y),(b,x)):(x,y)∈T} is a directed cut of K2→×D. Hence λ(K2→×D)≤2|T|=2λ(D).
LetTj be a directed cut of D that has size j, Cj be a strongly connected component of D-Tj with (Cj,D-Tj-Cj)=∅ (by Lemma 4.1 such components exist), Fj be an arc set of Cj such that Cj-Fj=(Xj,Yj;Ej) is a bipartite subgraph with bipartition (Xj,Yj). Then K2→×(Cj-Fj) consists of two components, whose vertex sets are {(a,x):x∈Xj}∪{(b,y):y∈Yj} and {(b,x):x∈Xj}∪{(a,y):y∈Yj}. It’s not difficult to see that the union of {((a,x),(b,y)):(x,y)∈Fj∩A(D[Xj])}, {((b,x),(a,y)):(x,y)∈Fj∩A(D[Yj])}, {((a,x),(b,y)):(x,y)∈(Xj,D-Cj)} and {((b,x),(a,y)):(x,y)∈(Yj,D-Cj)} is a directed cut of K2→×D, since its removal makes {(a,y):y∈Yj}∪{(b,x):x∈Xj} not reachable from {(a,x):x∈Xj}∪{(b,y):y∈Yj}. Noticing that |{((a,x),(b,y)):(x,y)∈Fj∩A(D[Xj])}∪{((b,x),(a,y)):(x,y)∈Fj∩A(D[Yj])}|=|Fj|, |{((a,x),(b,y)):(x,y)∈(Xj,D-Cj)}∪{((b,x),(a,y)):(x,y)∈(Yj,D-Cj)}|=|Tj| and |Tj∪Fj|=|Tj|+|Fj|=j+βj, we deduce that λ(K2→×D)≤min{j+βj:λ(D)≤j≤δ}. And so, Claim  1 follows.
Claim  2.
λ
(
K
2
→
×
D
)
≥
min
{
2
λ
(
D
)
,
β
(
D
)
,
min
{
j
+
β
j
:
λ
(
D
)
≤
j
≤
δ
}.
LetS be a minimum direct cut of K2→×D, V1={x∈V(D): vertices (a,x) and (b,x) lie in common strongly connected component of K2→×D-S}, V2={x∈V(D): vertices (a,x) and (b,x) lie in different components of K2→×(D-S)}. Then (V1,V2) is a partition of V(D). From the minimality of S it follows that K2→×D-S consists of two strongly connected components, say C1 and C2. Noticing that (C1,C2)⊆S or (C2,C1)⊆S, we assume without loss of generality that (C1,C2)⊆S. Now three different cases occur: V1≠∅=V2; V1=∅≠V2; V1≠∅≠V2.
Consider at first the case whenV1≠∅=V2. By Lemma 2.1, we deduce that {x∈V(D):(a,x)∈V(C1)} induces a strongly connected component of D as well as {y∈V(D):(a,y)∈V(C2)} in this case. Furthermore, ({x∈V(D):(a,x)∈V(C1)},{y∈V(D):(a,y)∈V(C2)}) is a directed cut of D and ({(a,x):(a,x)∈V(C1)},{(b,y):(b,y)∈V(C2)})∪({(b,x):(b,x)∈V(C1)},{(a,y):(a,y)∈V(C2)})⊆S. It follows from these observations that
(4.1)|S|≥|{(a,x)∈V(C1)},{(b,y)∈V(C2)}|+|{(b,x)∈V(C1)},{(a,y)∈V(C2)}|≥2λ(D).
Consider secondly the case whenV1=∅≠V2. Let M={x∈V(D):(a,x)∈V(C1)} and N={y∈V(D):(b,y)∈V(C1)}. Then (M,N) is a partition of V(D) and (C1,C2)={((a,x),(b,y)):(x,y)∈A(D[M])}∪{((b,x),(a,y)):(x,y)∈A(D[N])}. Since D-A(D[M])-A(D[N]) is a bipartite subgraph of D, it follows that |(C1,C2)|=|A(D[M])|+|A(D[N])|≥β(D). Recalling that (C1,C2)⊆S, we have |S|≥|(C1,C2)|≥β(D).
Consider finally the case whenV1≠∅≠V2. Let
(4.2)H={x∈V(D):(a,x)∈V(C1),x∈V1},Q={x∈V(D):(a,x)∈V(C2),x∈V1},W={x∈V(D):(a,x)∈V(C1),x∈V2},Z={x∈V(D):(a,x)∈V(C2),x∈V2}.
Then(H,Q,W,Z) is a partition of V(D), refer to (1) of Figure 2. Since (C1,C2)⊆S, the arcs in this set is removed in Figure 2. If H≠∅≠Q, then the set of arcs from {(a,x):x∈H}∪{(b,x):x∈H} to C2 is a directed cut of K2→×D, but it has less arcs than S. This contradiction shows that either H=∅ or Q=∅. Assume without loss of generality that Q=∅. Then K2→×D-S can be depicted as (2) of Figure 2.
On the one hand, for every arc(x,y)∈(H,D-H), if y∈W then ((a,x),(b,y))∈S; if y∈Z then ((b,x),(a,y))∈S. On the other hand, for every arc (x,y)∈A(D[W]) the arc ((a,x),(b,y))∈S and for every arc (x,y)∈A(D[Z]) the arc ((b,x),(a,y))∈S. It follows from these observations that
(4.3)|S|≥|[H,D-H]|+(|A(D[W])|+|A(D[Z])|)≥min⁡⁡{j+βj:λ(D)≤j≤δ(D)},
where [H,D-H] represents the set of arcs with ends in H and D-H, respectively. And so, the theorem follows from Claims 1 and 2.



---

*Source: 424023-2012-07-30.xml*