Superconnectivity of bipartite digraphs and graphs (Q1292813): Difference between revisions

A maximally connected digraph \(D\) is said to be super-\(\kappa\) if all its minimum disconnecting sets are trivial. Analogously, \(D\) is called super-\(\lambda\) if it is maximally arc-connected and all its minimum arc-disconnecting sets are trivial. The authors prove that any bipartite digraph \(D\) with diameter \(d\) is (i) super-\(\kappa\) if \(d\leq 2\ell-1\), and (ii) super-\(\lambda\) if \(d\leq 2\ell\), where \(\ell\) denotes a parameter related to the number of short paths. Moreover, these results are the best possible. Similar results are given for bipartite graphs.