Cyclic arc-connectivity in a Cartesian product digraph

✍ Scribed by Zhao Zhang; Yufang Zhu

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 319 KB
• Volume: 23
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2010.03.013

✦ Synopsis

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 λ c (D) is the minimum cardinality of all cycle separating arc-cuts. In this work, we study λ c (D) for the Cartesian product digraph D = D 1 × D 2 . We give a necessary and sufficient condition for D 1 × D 2 to be cycle separable, and show that λ c (D 1 × D 2 ) = 0 if D 1 × D 2 is cycle separable but not strongly connected. For the case where D = D 1 × D 2 is strongly connected, we give an upper bound and a lower bound for λ c (D). In particular, it can be determined that λ

min{n 1 , n 2 , . . . , n k }, where C n i is a directed cycle of length n i .