Lower bounds on the vertex-connectivity of digraphs and graphs

Since interconnection networks are often modeled by graphs or digraphs, the connectivity of a (di-)graph is an important measurement for fault tolerance of networks.Let G be a graph of order n, minimum degree δ, and vertex-connectivity κ. If G is not the complete graph, then Chartrand and Harary [G. Chartrand, F. Harary, Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61–63] proved in 1968 thatκ⩾2δ+2−n.κ⩾2δ+2−n. In 1993, Topp and Volkmann [J. Topp, L. Volkmann, Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695–700] proved the following analog bound for bipartite graphs. If G   is a bipartite graph with κ<δκ<δ, thenκ⩾4δ−n.κ⩾4δ−n. In this paper we present some generalizations and extensions of these inequalities for digraphs as well as for graphs.