Cyclic arc-connectivity in a Cartesian product digraph

A digraph DD is cycle separable if it contains two vertex disjoint directed cycles. For a cycle separating digraph DD, an arc set SS is a cycle separating arc-cut if D−SD−S has at least two strong components containing directed cycles. The cyclic arc-connectivity λc(D)λc(D) is the minimum cardinality of all cycle separating arc-cuts. In this work, we study λc(D)λc(D) for the Cartesian product digraph D=D1×D2D=D1×D2. We give a necessary and sufficient condition for D1×D2D1×D2 to be cycle separable, and show that λc(D1×D2)=0λc(D1×D2)=0 if D1×D2D1×D2 is cycle separable but not strongly connected. For the case where D=D1×D2D=D1×D2 is strongly connected, we give an upper bound and a lower bound for λc(D)λc(D). In particular, it can be determined that λc(Cn1×Cn2×⋯×Cnk)=(k−1)min{n1,n2,…,nk}λc(Cn1×Cn2×⋯×Cnk)=(k−1)min{n1,n2,…,nk}, where CniCni is a directed cycle of length nini.