Restricted arc-connectivity of generalized tournaments
Dirk Meierling, Lutz Volkmann, Stefan Winzen · 2008
If D is a strongly connected digraph, then an arc set S of D is called a restricted arc-cut of D if D − S has a non-trivial strong component D1 such that D − V (D1) contains an arc. Recently, Volkmann [12] defined the restricted arc-connectivity λ ′ (D) as the minimum cardinality over all restricted arc-cuts S. A strongly connected digraph D is called λ ′-connected when λ ′ (D) exists. Let k ≥ 2 be an integer. An arc set S of D is a k-restricted arc-cut of D if D − S contains at least k non-trivial strong components. Volkmann [Inform. Process. Lett. 103 (2007), 234– 239] also defined the k-restricted arc-connectivity λ ′ k (D) as the minimum cardinality over all k-restricted arc-cuts S. A strongly connected digraph (D) exists. D is called λ ′ k-connected when λ ′ k In this paper we characterize all λ ′-connected tournaments, multipartite tournaments, local tournaments and in-tournaments. In addition, we determine the λ ′ 2-connected tournaments and local tournaments.