Minimax properties of some density measures in graphs and digraphs

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.

KEYWORDS:

• Minimax theorems
• maximum subdigraph arc-strong connectivity
• maximum subdigraph out-degree
• slicing
• restricted edge-connectivity

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.

Additional information

Funding

Xiaoxia Lin's research is partially supported by the Natural Science Foundation of Fujian Province of China (No.2016J01666); and Hong-Jian Lai's research is partially supported by National Natural Science Foundation of China grants CNNSF 11771039 and CNNSF 11771443.