ABSTRACT
For a graph G, let denote the connectivity , or the edge-connectivity , or the minimum degree of G, and define is a subgraph of . Matula in [K-components, clusters, and slicings in graphs, SIAM J. Appl. Math. 22 (1972), pp. 459–480] proved two minimax theorems related to and , and obtained polynomial algorithms to determine , and . The restricted edge-connectivity of G, denoted by , is the minimum size of a restricted edge-cut of G. We define . For a digraph D, let , , and denote the strong connectivity, arc-strong connectivity, minimum in-degree and out-degree of D, respectively. For each , define is a subdigraph of . In this paper, we obtain analogous minmax duality results, which are applied to yield polynomial algorithms to determine , , and for a digraph D and for a graph G.
Acknowledgements
We would like to thank Dr George Loizou for drawing our attention to other related developments and the existence of better performed algorithms, and for his useful suggestions to improve this paper.
Disclosure statement
No potential conflict of interest was reported by the authors.