Bipartite graphs and digraphs with maximum connectivity (Q1923586): Difference between revisions

For a given bipartite digraph with diameter \(D\), let \(\ell\), \(1\leq \ell\leq D\), be the greatest integer such that for any two vertices \(x\) and \(y\) at distance \(d(x, y)\leq \ell\), the shortest \(x\)-\(y\) path is unique. The authors show that if the minimum degree \(\delta>1\) then the vertex connectivity \(\kappa=\delta\) whenever \(D\leq 2\ell\) and the edge connectivity \(\lambda=\delta\) whenever \(D\leq2\ell+1\). Analogous results are proved for bipartite graphs and for so-called superconnectivities.