Bounds on the k-restricted arc connectivity of some bipartite tournaments

摘要

For k ≥ 2, a strongly connected digraph D is called λk′-connected if it contains a set of arcs W such that D−W contains at least k non-trivial strong components. The k-restricted arc connectivity of a digraph D was defined by Volkmann as λk′(D)=min{|W|:Wisak-restrictedarc-cut}. In this paper we bound λk′(T) for a family of bipartite tournaments T called projective bipartite tournaments. We also introduce a family of “good” bipartite oriented digraphs. For a good bipartite tournament T we prove that if the minimum degree of T is at least 1.5k−1 then k(k−1)≤λk′(T)≤k(N−2k−2), where N is the order of the tournament. As a consequence, we derive better bounds for circulant bipartite tournaments.