Weak connectedness of tensor product of digraphs

Weak connectedness of tensor product of digraphs

Discrete Applied Mathematics ( ) – Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locat...

330KB Sizes 0 Downloads 2 Views

Discrete Applied Mathematics (

)



Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

Weak connectedness of tensor product of digraphs Sheng Chen ∗ , Xiaomei Chen Department of Mathematics, Harbin Institute of Technology, Harbin 150001, China

article

abstract

info

Article history: Received 3 June 2014 Received in revised form 13 November 2014 Accepted 16 December 2014 Available online xxxx

In this paper we give a complete characterization for digraphs whose tensor product is weakly connected, which solves an open problem posed by Harary and Trauth (1966). © 2014 Elsevier B.V. All rights reserved.

Keywords: Tensor product Weak connectedness Chainable matrix Weight

1. Introduction For the notation and terminology below on digraphs, see [1,4,9]. A digraph D is a pair D = (V (D), E (D)) with E (D) ⊆ V (D) × V (D). For an arc (u, v) ∈ E (D), u is said to be the initial vertex of the arc and v the end vertex. The out-degree (resp. indegree) of a vertex v ∈ V (D) is defined to be the number of arcs having v as an initial (resp. end) vertex. A source (resp. sink) is a vertex with in-degree (resp. out-degree) equal to 0. The directed cycle Cn is the digraph with vertex set [n] = {1, 2, . . . , n} and arc set {(1, 2), (2, 3), . . . , (n, 1)}. In particular, C1 consists of a single vertex with a loop. The directed path Pn is Cn with the arc (n, 1) removed. The length of a directed cycle or path is defined to be the number of arcs it contains. A digraph D is called in-functional (resp. out-functional) if the out-degree (resp. in-degree) of each vertex in D equals to 1. Note that the concept of in-functional digraphs here coincides with the concept of functional digraphs in [5]. For k ≥ 1, a route of length k in D from v1 to vk+1 is a pair L = (S , σ ), where S = (v1 , v2 , . . . , vk+1 ) is a sequence of k + 1 vertices in D, and σ = (σ1 , σ2 , . . . , σk ) is a sequence consisting of 1 and −1, such that

σi = 1 =⇒ (vi , vi+1 ) ∈ E (D),

and

σi = −1 =⇒ (vi+1 , vi ) ∈ E (D).

We call v1 the initial vertex of L, and vk+1 the end vertex. L is said to be closed if v1 = vk+1 , and alternating if σi = (−1)i for k 1 ≤ i ≤ k. The type and weight of L are defined to be σ and i=1 σi respectively. The greatest common divisor (abbreviated GCD) of the weights of all closed routes in D is called the weight of D, where we define GCD(0, 0) = 0. Let w(D) denote the weight of D. Then we have w(D) = 0 if all closed routes in D have weight 0. Let L = (S , σ ) be a route with S = (v1 , . . . , vk+1 ) and σ = (σ1 , . . . , σk ). Let R = (T , τ ) be another route with T = (u1 , . . . , ul+1 ) and τ = (τ1 , . . . , τl ). If vk+1 = u1 , then the composite route LR is defined to be LR = ((v1 , . . . , vk+1 , u2 , . . . , ul+1 ), (σ1 , . . . , σk , τ1 , . . . , τl )).



Corresponding author. E-mail addresses: [email protected] (S. Chen), [email protected] (X. Chen).

http://dx.doi.org/10.1016/j.dam.2014.12.016 0166-218X/© 2014 Elsevier B.V. All rights reserved.

2

S. Chen, X. Chen / Discrete Applied Mathematics (

(a) D1 .

(b) D2 .

)

(c) D3 .



(d) D1 ⊗ D2 .

Fig. 1. Examples of weights and tensor product.

A walk is a route with type (1, 1, . . . , 1). There are three kinds of connectedness for digraphs defined as follows. A digraph is said to be strong (strongly connected) if for each pair u, v of its vertices, there is a walk from u to v and a walk from v to u. It is unilateral (unilaterally connected) if for each pair u, v of its vertices, there is a walk from u to v or a walk from v to u. It is weak (weakly connected) if for each pair u, v of its vertices, there is a route from u to v . Note that the digraph P1 is not weak. If D is a weak digraph with w(D) = 0, then for any u, v ∈ V (D), all routes in D from u to v have the same weight, which we denote by w(u, v), and we define the diameter of D to be d(D) = max{w(u, v)|u, v ∈ V (D)}. Let D1 and D2 be digraphs. Their tensor product D1 ⊗ D2 is defined to be the digraph with vertex set V1 × V2 , and ((u1 , v1 ), (u2 , v2 )) is an arc in D1 ⊗ D2 precisely if (u1 , u2 ) and (v1 , v2 ) are arcs in D1 and D2 respectively. See [8] for more details. Note that we also use the symbol ⊗ for the matrix tensor in this paper. Example 1. We consider the weights of digraphs in Fig. 1. Let W (D) denote the set consisting of weights of closed routes in D with no repeated vertices, other than the repetition of the initial and end vertices. Then we have W (D1 ) = {0, ±2}, W (D2 ) = {0, ±1, ±3, ±4} and W (D3 ) = {0}. Thus w(D1 ) = 2, w(D2 ) = 1 and w(D3 ) = 0. Since L = ((5, 6, 3, 2), (1, 1, 1)) is one of the routes in D3 with maximal weight, we have d(D3 ) = 3. The digraph in Fig. 1(d) is the tensor product of D1 and D2 , where we use ij to denote the vertex (i, j). Considering the connectedness of the tensor product of digraphs, three problems arise naturally: characterize digraphs whose tensor product has each of the three kinds of connectedness. McAndrew [8] solved one of the problems by characterizing digraphs whose tensor product is strong. Harary and Trauth [6] solved the problem for a unilaterally connected tensor product. The problem for a weakly connected tensor product was introduced and analyzed in [6]. Hartfiel and Maxson [7] gave a partial answer to this problem by showing that D1 ⊗ D2 is weak for any weak digraph D1 if and only if D2 is chainable. Blondel et al. [2] noticed that this problem is equivalent to characterizing digraphs whose similarity matrices have only positive entries. Despite these contributions on this problem, a convenient characterization for a weakly connected tensor product of digraphs is, to our knowledge, still open. In this paper, we solve the above problem posed by Harary and Trauth. Let D1 and D2 be weak digraphs. In Section 2, we consider the case when D1 and D2 are both in-functional or out-functional, and show that D1 ⊗ D2 is weak if and only if the GCD of their weights is 1. In Section 3, we consider the case when D2 is a directed path of length l, and show that D1 ⊗ D2 is weak if and only if D1 is l-chainable. In Section 4, we show that the connectedness of the tensor product of two general weak digraphs can be reduced to one of the above two cases, and give a complete characterization for a weakly connected tensor product of digraphs in Theorem 15 and Corollary 16. 2. Tensor product of functional digraphs Let L = ((u1 , . . . , uk ), σ ) and R = ((v1 , . . . , vk ), σ ) be routes with the same type in D1 and D2 respectively. Then L and (L,R)

R determine bijectively a route L0 = (((u1 , v1 ), . . . , (uk , vk )), σ ) in D1 ⊗ D2 , which we denote by (u1 , v1 ) −−→ (uk , vk ). We call L and R the projections of L0 to D1 and D2 respectively. Example 2. Let L = ((1, 2, 1, 2), (1, 1, −1)) and R = ((1, 2, 3, 1), (1, 1, −1)) be routes in D1 and D2 respectively in Fig. 1. (L,R)

Then we have (1, 1) −−→ (2, 1) = (((1, 1), (2, 2), (1, 3), (2, 1)), (1, 1, −1)) being a route from (1, 1) to (2, 1) in D1 ⊗ D2 . The following result gives a necessary condition for a weak tensor product. Lemma 3. Let D1 and D2 be digraphs with w(D1 ) = d1 and w(D2 ) = d2 . If D1 ⊗ D2 is weak, then GCD(d1 , d2 ) = 1. (L,R)

Proof. Let u ∈ V (D1 ) and (v1 , v2 ) ∈ E (D2 ). Since D1 ⊗ D2 is weak, there is a route (u, v1 ) −−→ (u, v2 ) from (u, v1 ) to (u, v2 ) ←−− for some routes L and R. Let w be the weight of L. Then L is a closed route in D1 with weight w , and Rv2 v1 is a closed route ← − − in D2 with weight w − 1, where v2 v1 denotes the route ((v2 , v1 ), (−1)). Since GCD(w, w − 1) = 1, the result follows.  A directed in-rooted (resp. out-rooted) tree is a weak digraph with the out-degree (resp. in-degree) of one distinguished vertex, called the root, equal to 0, and the out-degree (resp. in-degree) of other vertices equal to 1. By [5, Theorem 1], a weak in-functional digraph consists of a directed cycle Cp , called the underlined cycle of the digraph, and some directed in-rooted

S. Chen, X. Chen / Discrete Applied Mathematics (

)



3

Fig. 2. (a) In-functional digraph with underlined cycle C4 ; (b) Out-functional digraph with underlined cycle C4 .

trees attached to vertices of the cycle. Similarly, a weak out-functional digraph consists of an underlined cycle and some directed out-rooted trees attached to vertices of the cycle. See Fig. 2 for instance. The main result of this section is stated as follows. Lemma 4. Let D1 and D2 be both weak in-functional (or out-functional) digraphs with w(D1 ) = d1 and w(D2 ) = d2 . Then D1 ⊗ D2 is weak if and only if GCD(d1 , d2 ) = 1. Moreover, if D1 ⊗ D2 is weak, then w(D1 ⊗ D2 ) = d1 d2 . Proof. The only if part follows from Lemma 3. For the if part, we just show the result for in-functional digraphs, the case of out-functional digraphs being entirely similar. Let C and C ′ be the underlined cycles of D1 and D2 respectively. Then C ∼ = Cd1 (L,R)

and C ′ ∼ = Cd2 . For any vertices u1 ∈ V (D1 ) and v1 ∈ V (D2 ), there exists a route (u1 , v1 ) −−→ (u2 , v2 ) for some routes L and R, such that u2 ∈ V (C ) and v2 ∈ V (C ′ ). Thus to show that D1 ⊗ D2 is weak, it suffices to prove that for any u3 ∈ V (C ) and v3 ∈ V (C ′ ), there exist routes L′ from u2 to u3 and R′ from v2 to v3 with the same type in C and C ′ respectively, which is (L′ ,R′ )

equivalent to saying that (u2 , v2 ) −−−→ (u3 , v3 ) is a route in C ⊗ C ′ . Since GCD(d1 , d2 ) = 1, we know that C ⊗ C ′ ∼ = Cd1 d2 is weak (see [4], Eq. (32.1)), and the result follows. We now consider the weight of D1 ⊗ D2 . Since GCD(d1 , d2 ) = 1 and any closed route in D1 ⊗ D2 projects to each Di as a route with the same type, we have d1 d2 |w(D1 ⊗ D2 ). On the other hand, C ⊗ C ′ ∼ = Cd1 d2 is a subdigraph of D1 ⊗ D2 , which implies that w(D1 ⊗ D2 )|d1 d2 . Thus we have w(D1 ⊗ D2 ) = d1 d2 .  3. Tensor product of digraphs with directed paths Chainable matrices were first introduced and characterized by Hartfiel and Maxson [7, Lemma 1.1]. A nonnegative matrix A is said to be chainable if it has no rows or columns of zeros, and there is no pair of permutation matrices M and N so that MAN has the block form



A1 MAN = 0



0 . A2

Note that we assume A to be a nonnegative matrix here instead of (0, 1)-matrix. Since A is chainable if and only if the matrix obtained from A with all nonzero entries replaced by 1 is chainable, all results about chainable matrices in [7] still hold. For a digraph D with V (D) = [n], the adjacency matrix A(D) = (aij ) of D is formed by setting ai,j = 1 if (i, j) is an arc in D. We extend the concept of chainable matrices as follows. Definition 5. Let A be a nonnegative square matrix and l a positive integer. Then A is said to be l-chainable if Al is chainable. In particular, a digraph is said to be l-chainable if its adjacency matrix is l-chainable. Lemma 6. Let D be a digraph and l a positive number. If D is l-chainable, then D is weak and contains no sources or sinks. Proof. Let A be the adjacency matrix of D. If D is not weak, then there exists a permutation matrix M such that MAM ′ =



A1 0

0 A2



with A1 and A2 square. Thus MAl M ′ is block diagonal, which implies that D is not l-chainable. If D contains sources (resp. sinks), then A has some columns (resp. rows) of zeros, which implies that Al has some columns (resp. rows) of zeros. Thus D is not l-chainable.  For the tensor product of chainable matrices we have the following result. Lemma 7. Let A and B be nonnegative matrices. Then A ⊗ B is chainable if and only if A and B are both chainable.

4

S. Chen, X. Chen / Discrete Applied Mathematics (

)



Proof. The if part follows from [7, Theorem 2.3]. For the only if part, we assume that one of A and B, say A, is not chainable. If A has rows or columns of zeros, then A ⊗ B also has rows or columns of zeros, which implies that A ⊗ B is not chainable. If A has no rows or columns of zeros, then there exist permutation matrices M and N such that MAN has the block form

 MAN =

A1 0



0 . A2

Suppose B is an m by n matrix. Let M1 = M ⊗ Im and N1 = N ⊗ In . Then M1 (A ⊗ B)N1 = (MAN ) ⊗ B =



A1 ⊗ B 0

which also implies that A ⊗ B is not chainable.

0



A2 ⊗ B

,



The competition graph of a digraph D, denoted by C (D), is an undirected graph with the same vertex set as D, and there is an edge between vertices u and v if and only if (u, x) and (v, x) are arcs of D for some vertex x. See [3] for more details. Lemma 8. Let D be a digraph without sources or sinks. Then D is chainable if and only if C (D) is connected. Proof. Suppose V (D) = [n]. Let A be the adjacency matrix of D. We denote by C ∗ (A) the column graph of A, i.e., C ∗ (A) has vertex set [n], and there is an edge between i and j if and only if A(k, i)A(k, j) ̸= 0 for some k ∈ [n]. By the definition of competition graph, the set {i ∈ [n]|(i, j) ∈ E (D)} with j fixed induces a clique in C (D), which we denote by Dj . Since Di and Dj have a vertex in common if and only if A(k, i)A(k, j) ̸= 0 for some k ∈ [n], we know that C (D) is connected if and only if C ∗ (A) is connected. If C (D) is not connected, then C ∗ (A) is also not connected, and we can partition V (C ∗ (A)) into two nonempty disjoint sets, say S1 and S2 , such that there is no edge between S1 and S2 , i.e., for any i ∈ S1 and j ∈ S2 , we have A(k, i)A(k, j) = 0 for 1 ≤ k ≤ n. Let T1 = {i|A(i, j) ̸= 0 for some j ∈ S1 } and T2 = {i|A(i, j) ̸= 0 for some j ∈ S2 }. Then T1 T2 = φ . Let P and Q be permutation matrices such that the first |S1 | columns of PAQ are indexed by S1 and the first |T1 | rows of PAQ are indexed by T1 . Then PAQ is block diagonal, which implies that D is not chainable. On the other hand, if D is not chainable, then MAN is block diagonal for some permutation matrices M and N, which implies that C ∗ (MAN ) is not connected. Since C ∗ (A) is isomorphic to C ∗ (MAN ), we know that C ∗ (A), and thus C (D), is not connected.  Now we are ready to give the main result of this section. Lemma 9. Let D be a digraph and l a positive integer. Then D ⊗ Pl+1 is weak if and only if D is l-chainable. Proof. Suppose V (D) = [n]. Let A be the adjacency matrix of D. Recall that D ⊗ Pl+1 is the digraph with vertex set [n]×[l + 1], and ((a, i), (b, j)) is an arc of D ⊗ Pl+1 if and only if (a, b) ∈ E (D) and j = i + 1. If a is a source (resp. sink) in D, then (a, l + 1) (resp. (a, 1)) is an isolated vertex in D ⊗ Pl+1 , which implies that D ⊗ Pl+1 is not weak. Thus by Lemma 6, we can assume that D contains no sources or sinks. Let Sa be the set consisting of paths of length l in D ⊗ Pl+1 containing vertex (a, 1).  D is defined to be the undirected graph with vertex set V ( D) = {Sa |a ∈ V (D)}, and there is an edge between Sa and Sb with a ̸= b if and only if for some paths P ∈ Sa and P ′ ∈ Sb , P and P ′ have a vertex in common. Since D contains no sources or sinks, every vertex of D ⊗ Pl+1 is contained in a path of Sa for some a ∈ [n]. Thus D ⊗ Pl+1 is weak if and only if  D is connected. We denote by Dl the digraph with vertex set [n], and (i, j) is an arc of Dl if and only if Al (i, j) ̸= 0. By the definition of competition graph, there is an edge between i and j in C (Dl ) if and only if there exist walks from i to k and j to k respectively with length l for some k ∈ [n], which is equivalent to saying that there is an edge between Si and Sj in  D. Thus we have l l l  D∼ C ( D ) , which implies that D ⊗ P is weak if and only if C ( D ) is connected. Since D contains no sources or sinks, we = l +1 know by Lemma 8 that C (Dl ) is connected if and only if Dl is chainable. Then the result follows from the simple fact that Dl is chainable if and only if Al is chainable.  4. Main results Let D be a digraph and ∼ an equivalence relation on V (D). We denote by V (D)/∼ the set of ∼-equivalence classes, and by D/∼ the quotient digraph with vertex set V (D)/∼, such that for α, β ∈ V (D)/∼, (α, β) is an arc in D/∼ if and only if there exist u1 ∈ α and u2 ∈ β with (u1 , u2 ) an arc in D. Towber [9, Definition 4.2] defined two kinds of quotient digraphs as follows. Definition 10. Let D be a digraph. We denote by ∼l the smallest equivalence relation on V (D) such that

(u, v1 ) ∈ E (D) and (u, v2 ) ∈ E (D) =⇒ v1 ∼l v2 ; and we define CL (D) := D/∼l . Similarly, ∼r is the smallest equivalence relation on V (D) such that

(u1 , v) ∈ E (D) and (u2 , v) ∈ E (D) =⇒ u1 ∼r u2 ; and we define CR (D) := D/∼r .

S. Chen, X. Chen / Discrete Applied Mathematics (

(a) CL (D2 ).

(b) CL2 (D2 ).

)



5

(c) CL3 (D2 ) = CL∞ (D2 ).

Fig. 3. The quotient digraphs CLm (D2 ) (m ≥ 1).

We omit the proof of the next result which follows readily from the above definition. Lemma 11. Let D be a digraph. (1) If D is weak, then CL (D) and CR (D) are both weak. (2) If D contains no sources (resp. sinks), then both CL (D) and CR (D) contain no sources (resp. sinks). Let fl be the homomorphism of digraphs from D to CL (D) defined by fl (u) = α , where α is the equivalence class containing u. For a route L = ((u1 , . . . , uk+1 ), σ ) in D, we denote by fl (L) the route fl (L) = ((fl (u1 ), . . . , fl (uk+1 )), σ ) in CL (D). The homomorphism fr is defined for CR (D) in a similar way. Let R = ((α1 , . . . , αk+1 ), (σ1 , . . . , σk )) be a route in CL (D). For u ∈ α1 and v ∈ αk+1 , we lift R to a route in D from u to v as follows. By Definition 10, there exist ui , vi ∈ αi (1 ≤ i ≤ k + 1) with u1 = u and vk+1 = v , such that ei = ((vi , ui+1 ), (σi ))(1 ≤ i ≤ k) is a route in D. For 1 ≤ i ≤ k + 1, if ui ̸= vi , then there exists an alternating route Ri in D from ui to vi with even length; if ui = vi , we define Ri to be the virtual route consisting of the single vertex ui , i.e., Ri = ((ui ), (φ)), where φ denotes the empty set. Then R(u, v) = R1 e1 R2 e2 · · · Rk ek Rk+1 is a route in D from u to v , which we call a lifting of R. It is obvious that R(u, v) has the same weight as R. Routes in CR (D) can be lifted to routes in D similarly. Lemma 12. Let D be a digraph. Then w(CL (D)) = w(CR (D)) = w(D). Proof. We just show w(CL (D)) = w(D), the proof for w(CR (D)) = w(D) being entirely similar. For any closed route L in D, fl (L) is a closed route in CL (D) with the same type, which implies w(CL (D))|w(D). On the other hand, for any closed route R in CL (D), we can lift R to a closed route in D with the same weight, which implies w(D)|w(CL (D)). Thus we have w(CL (D)) = w(D).  Let D be a digraph. The quotient digraph CLm (D) is defined recursively by CLm (D) := CL (CLm−1 (D)). Then the digraphs CLm (D) all coincide for m sufficiently large, and we denote this stable digraph by CL∞ (D). The stable digraph CR∞ (D) is defined similarly. See Fig. 3 for the quotient digraphs CLm (D2 ) of the digraph D2 in Fig. 1. Lemma 13. Let D be a weak digraph with w(D) = d and d(D) = l. (1) If d ̸= 0, then CL∞ (D) (resp. CR∞ (D)) is an in-functional (resp. out-functional) digraph with underlined cycle Cd , and CR∞ CL∞ (D) is the directed cycle Cd . (2) If d = 0, then CR∞ CL∞ (D) is the directed path Pl+1 . Proof. (1) By Lemmas 11 and 12, CL (D) is a weak digraph with w(CL∞ (D)) = w(D) ̸= 0. Since the out-degree of each vertex in CL∞ (D) is not greater than 1, we know that CL∞ (D) is an in-functional digraph with underlined cycle Cd . The results for CR∞ (D) and CR∞ CL∞ (D) can be proved similarly. (2) By Lemmas 11 and 12, we know that CR∞ CL∞ (D) is a weak digraph with w(CR∞ CL∞ (D)) = w(D) = 0. Since the out-degree and in-degree of each vertex in CR∞ CL∞ (D) are not greater than 1, it should be a directed path. Thus it suffices to show d(D) = d(CL (D)) = d(CR (D)). For any route L in D, fl (L) is a route in CL (D) with the same type, which implies that d(CL (D)) ≥ d(D). On the other hand, any route in CL (D) can be lifted to a route in D with the same weight, which implies that d(D) ≥ d(CL (D)). Thus we have d(D) = d(CL (D)). The proof for d(D) = d(CR (D)) is similar.  Lemma 14. Let D1 and D2 be digraphs. If D1 contains no sources (resp. sinks), then we have the following result. (1) D1 ⊗ D2 is weak if and only if D1 ⊗ CL∞ (D2 ) (resp. D1 ⊗ CR∞ (D2 )) is weak. (2) w(D1 ⊗ D2 ) = w(D1 ⊗ CL∞ (D2 )) (resp. w(D1 ⊗ D2 ) = w(D1 ⊗ CR∞ (D2 ))). Proof. We just consider the case for D1 without sources, the case for D1 without sinks being similar. (1) By Lemma 11, it suffices to show that D1 ⊗ D2 is weak if and only if D1 ⊗ CL (D2 ) is weak. Let u, u′ ∈ V (D1 ), v, v ′ ∈ V (D2 ) and α, β ∈ V (CL (D2 )) with v ∈ α and v ′ ∈ β . (L,R)

If D1 ⊗ D2 is weak, then there exists a route (u, v) −−→ (u′ , v ′ ) in D1 ⊗ D2 for some routes L in D1 and R in D2 with the (L,fl (R))

same type, which implies that (u, α) − −−−→ (u′ , β) is a route in D1 ⊗ CL (D2 ), thus D1 ⊗ CL (D2 ) is weak.

6

S. Chen, X. Chen / Discrete Applied Mathematics (

)



(L,R)

On the other hand, if D1 ⊗ CL (D2 ) is weak, then there is a route (u, α) −−→ (u′ , β) in D1 ⊗ CL (D2 ) for some routes L in D1 and R in CL (D2 ) with the same type. Suppose that L = ((u1 , . . . , uk+1 ), σ ) and R = ((α1 , . . . , αk+1 ), σ ), where u1 = u, uk+1 = u′ , α1 = α and αk+1 = β . Let R(v, v ′ ) = R1 e1 R2 e2 · · · Rk ek Rk+1 be a lifting of R. Since D1 contains no sources, there exist wi (1 ≤ i ≤ k + 1) with (wi , ui ) an arc in D1 . For 1 ≤ i ≤ k + 1, if Ri is a virtual route, then we define Li to be the virtual route ((ui ), (φ)); otherwise, we define Li = (S , σ ) be the route in D1 with S = (ui , wi , ui , . . . , wi , ui ) and σ = (−1, 1, . . . , −1, 1), such that Li has the same type as Ri . Let e′i denote the route ((ui , ui+1 ), (σi )). Then L(u, u′ ) = (L(u,u′ ),R(v,v ′ ))

L1 e′1 L2 e′2 · · · Lk e′k Lk+1 is a route in D1 from u to u′ with the same type as R(v, v ′ ), thus we have (u, v) −−−−−−−−→ (u′ , v ′ ) a route in D1 ⊗ D2 , which implies that D1 ⊗ D2 is weak. (2) By the above proof, any closed route in D1 ⊗ D2 is corresponding to a closed route in D1 ⊗ CL (D2 ) with the same type, and any closed route in D1 ⊗ CL (D2 ) can be lifted to a closed route in D1 ⊗ D2 with the same weight. Thus we have w(D1 ⊗ D2 ) = w(D1 ⊗ CL (D2 )).  We are now ready to give the main results of this paper. By Lemma 3, the tensor product of digraphs is not weak if all factors have weight 0. Thus we always assume that at least one digraph in the product has nonzero weight in the following part. Theorem 15. Let D1 and D2 be weak digraphs with w(D1 ) = d1 and w(D2 ) = d2 . Then we have the following result. (1) If d1 d2 ̸= 0, then D1 ⊗ D2 is weak if and only if (i) GCD(d1 , d2 ) = 1, (ii) one of Di (i = 1, 2) containing sources (resp. sinks) implies that the other contains no sinks (resp. sources). Moreover, if D1 ⊗ D2 is weak, then w(D1 ⊗ D2 ) = d1 d2 . (2) If one of di , say d1 , equals to 0, then D1 ⊗ D2 is weak if and only if D2 is l-chainable, where l = d(D1 ). Proof. (1) If D1 contains a source (resp. sink) u and D2 contains a sink (resp. source) v , then (u, v) is an isolated vertex in D1 ⊗ D2 , which implies that D1 ⊗ D2 is not weak. Thus we just need to consider the following three cases. (a) Both of D1 and D2 contain no sources. In this case, we know by Lemma 14 that D1 ⊗ D2 is weak if and only if CL∞ (D1 ) ⊗ CL∞ (D2 ) is weak. By Lemma 13, CL∞ (D1 ) and CL∞ (D2 ) are in-functional digraphs with underlined cycles Cd1 and Cd2 respectively. Thus by Lemma 4, D1 ⊗ D2 is weak if and only if GCD(d1 , d2 ) = 1, and w(D1 ⊗ D2 ) = d1 d2 if D1 ⊗ D2 is weak. (b) Both of D1 and D2 contain no sinks. The discussion for this case is entirely similar as in (a). (c) One of Di , say D1 , contains no sources or sinks. In this case, we know by Lemma 14 that D1 ⊗ D2 is weak if and only if D1 ⊗ CR∞ CL∞ (D2 ) ∼ = D1 ⊗ Cd2 is weak, which, by using Lemma 14 again, is equivalent to saying that CR∞ CL∞ (D1 ) ⊗ ∼ Cd2 = Cd1 ⊗ Cd2 is weak. Thus D1 ⊗ D2 is weak if and only if GCD(d1 , d2 ) = 1, and w(D1 ⊗ D2 ) = d1 d2 if D1 ⊗ D2 is weak. (2) Since d1 = 0, there exist sources and sinks in D1 . Thus we can assume that D2 contains no sources or sinks. By Lemmas 13 and 14, D1 ⊗ D2 is weak if and only if CR∞ CL∞ (D1 ) ⊗ D2 ∼ = Pl+1 ⊗ D2 is weak, where l = d(D1 ). Then the result follows from Lemma 9.  As a direct consequence of Theorem 15, we have the following result for the tensor product of m ≥ 2 digraphs. Corollary 16. Let Di be a weak digraphs with w(Di ) = di , i = 1, 2, . . . , m. (1) If di ̸= 0 (i = 1, 2, . . . , m), then D1 ⊗ D2 ⊗ · · · ⊗ Dm is weak if and only if (i) d1 , d2 , . . . , dm are pairwise relatively prime, (ii) one of Di (i = 1, 2, . . . , m) containing sources (resp. sinks) implies that the others contain no sinks (resp. sources). (2) If one of di , say d1 , is 0, then D1 ⊗ D2 ⊗ · · · ⊗ Dm is weak if and only if Di (i = 2, 3, . . . , m) is l-chainable, where l = d(D1 ). Proof. (1) The result follows from Theorem 15 directly. (2) Let Ai be the adjacency matrix of Di . By Theorem 15, D1 ⊗ D2 ⊗ · · · ⊗ Dm is weak if and only if D2 ⊗ · · · ⊗ Dm is l-chainable, which is equivalent to say that Al2 ⊗ · · · ⊗ Alm is chainable. Then the result follows from Lemma 7.  Acknowledgments Part of the work was done while the second author visited the MIT Mathematics Department during the academic year 2012–2013. The second author warmly thanks Richard Stanley for his hospitality. The authors thank the editors and referees for their valuable comments and helpful suggestions on the first version of this paper. The first author was supported by National Natural Science Foundation of China (Grant No. 11001064), by the Fundamental Research Funds for the Central Universities (Grant No. HIT. NSRIF. 2014085), and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.

S. Chen, X. Chen / Discrete Applied Mathematics (

)



7

References [1] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London, 2000. [2] V.D. Blondel, A. Gajardo, M. Heymans, P. Senellart, P.V. Dooren, A measure of similarity between graph vertices: applications to synonym extraction and web searching, SIAM Rev. 46 (4) (2004) 647–666. [3] J.E. Cohen, Interval graphs and food webs: a finding and a problem. Rand Corporation Document 17696-PR, Santa Monica, CA, 1968. [4] R. Hammack, W. Imrich, S. Klavzar, Handbook of Product Graphs, second ed., CRC Press, Boca Raton, FL, 2011. [5] F. Harary, The number of functional digraphs, Math. Ann. 188 (1959) 203–210. [6] F. Harary, C.A. Trauth Jr., Connectedness of products of two directed graphs, SIAM J. Appl. Math. 14 (1966) 250–254. [7] D. Hartfiel, C. Maxson, The chainable matrix, a special combinatorial matrix, Discrete Math. 12 (1975) 245–256. [8] M.H. McAndrew, On the product of directed graphs, Proc. Amer. Math. Soc. 14 (1963) 600–606. [9] J. Towber, Directed graphs and Kronecker invariants of pairs of matrices, J. Knot Theory Ramifications 17 (1) (2008) 75–132.