Connectivity of large bipartite digraphs and graphs (Q1377820): Difference between revisions

This paper studies the relation between the connectivity \(\kappa\) (edge-connectivity \(\lambda\)) and some other parameters of a bipartite graph or digraph \(G\). Namely, the order \(n\), minimum degree \(\delta\), maximum degree \(\Delta\), diameter \(D\), and a parameter \(\ell\) introduced by \textit{J. Fàbrega} and \textit{M. A. Fiol}, in [J. Graph Theory 13, 657-668 (1989; Zbl 0688.05029)] related to the number of short paths that exist between every pair of vertices. A main result reads: If \(G\) is a bipartite digraph with \(n>(\delta -1)(\Delta +\Delta^2+\cdots+\Delta^\ell +\Delta +\Delta^2+\cdots+\Delta^{D-\ell -1})+2\), then \(\kappa=\delta\). Similar results are proved for \(\lambda\) and also for the undirected case.