Cyclic Vertex-Connectivity Of Cartesian Product Digraphs

For a strongly connected digraph D = (V (D),A(D)), an vertex-cut S (?) V (D) isa cyclic vertex-cut of D if D - S has at least two strong components of order at least2. The cyclic vertex-connectivity is the minimum cardinality of all cyclic vertex-cuts.In this paper, we denote the cyclic vertex-connectivity of D asκc(D), and studyκc(D)for Cartesian product digraph D = D₁×D2, where D₁,D2 are two strongly connecteddigraphs. We give an upper boundκc(D)≤min{κ1n2,κ2n1,σ(D)} and a lower boundκc(D)≥min{κ1g2,κ2g1,M₁,M₂}, where ni is the order of Di. Let D₁^y and D₂^x denotesome of the D₁ and D2 copy, E(D₁),E(D2) denote the edge sets of D₁ and D2. Wesuppose that Di has connectivityκi > 0, order ni, and girth gi(i = 1, 2), and Di has non-trivial strong component. In particular, we are to determine the upper and lower boundofκc(C_n1×C_n2×...×C_nk), where Cni is a directed cycle of length ni, for i = 1, 2,...,k.This paper has three parts. In the first chapter, we introduce the background andthe main results. In the second chapter, we give an upper and lower bound ofκc(D). Inthe third chapter, we determine theκc(D) of C_n1×C_n2×...×C_nk.