Minimax properties of some density measures in graphs and digraphs. Issue 1 (2nd January 2018) - Anderson, Janet
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 .