Superconnectivity of bipartite digraphs and graphs (Q1292813): Difference between revisions
From MaRDI portal
Revision as of 21:35, 28 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Superconnectivity of bipartite digraphs and graphs |
scientific article |
Statements
Superconnectivity of bipartite digraphs and graphs (English)
0 references
9 August 1999
0 references
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.
0 references
superconnectivity
0 references
bipartite digraph
0 references
bipartite graphs
0 references