Connectivity of large bipartite digraphs and graphs Original Research Article

This paper studies the relation between the connectivity and other parameters of a bipartite (di)graph G. Namely, its order n, minimum degree δ, maximum degree Δ, diameter D, and a new parameter l related to the number of short paths in G. (When G is a bipartite — undirected — graph this parameter turns out to be l = (g − 2)/2, where g stands for its girth.) Let n(Δ, l)  1 + Δ + Δ2 + ··· + Δl. As a main result, it is shown that if n > (δ − 1){n(Δ, l) + n(Δ, D  l  1)  2} + 2, then the connectivity of the bipartite digraph G is maximum. Similarly, if n > (δ − 1){n(Δ, − l) + n(Δ, D − l − 2)}, then the arc-connectivity of G is also maximum. Some examples show that these results are best possible. Furthermore, we show that analogous results, formulated in terms of the girth, can be given for the undirected case.