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

摘要

Let D be a digraph of order n, minimum degree S and vertex-connectivity K. If D is not the complete digraph, then Geller and Harary [7] proved in 1971 that k≥2δ+2-n. An orientation of a simple graph is called an oriented graph. In this paper we present some improvements of the inequality K > 2(5+2 — n for oriented graphs as well as for bipartite oriented graphs. In particular, we show that k≥(4δ+2-n)/3 for an arbitrary oriented graph and k≥(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.