Lower bounds on the vertex-connectivity of oriented graphs and bipartite oriented graphs

Abstract

Let D be a digraph of order n, minimum degree δ and vertex-connectivity κ. If D is not the complete digraph, then Geller and Harary [7] proved in 1971 that κ ≥ 2δ + 2 - n. An orientation of a simple graph is called an oriented graph. In this paper we present some improvements of the inequality κ ≥ 2δ+2-n for oriented graphs as well as for bipartite oriented graphs. In particular, we show that κ ≥ 4δ+ 2-n/3 for an arbitrary oriented graph and κ ≥ 8δ-n/3 for every bipartite oriented graph. Moreover, sharp lower bounds for the vertex-connectivity, of general oriented graphs and bipartite oriented graphs, in terms of their degree sequences are derived.