Cyclic arc-connectivity in a Cartesian product digraph

摘要

A digraph D is cycle separable if it contains two vertex disjoint directed cycles. For a cycle separating digraph D, an arc set S is a cycle separating arc-cut if D S has at least two strong components containing directed cycles. The cyclic arc-connectivity lambda(c)(D) is the minimum cardinality of all cycle separating arc-cuts. In this work, we study lambda(c)(D) for the Cartesian product digraph D = D-1 x D-2. We give a necessary and sufficient condition for D-1 x D-2 to be cycle separable, and show that lambda(c)(D-1 x D-2) = 0 if D-1 x D-2 is cycle separable but not strongly connected. For the case where D = D-1 x D-2 is strongly connected, we give an upper bound and a lower bound for lambda(c)(D). In particular, it can be determined that lambda(c)(C-n1 x C-n2 x ... x C-nk) = (k - 1) min{n(1), n(2), ... , n(k)}, where C-ni is a directed cycle of length n(i).