Minimax properties of some density measures in graphs and digraphs

摘要

For a graph G, let f(G) denote the connectivity k(G), or the edge-connectivity k'(G), or the minimum degree δ(G) of G, and define f(G) = max{f(H): H is a subgraph of G}. Matula in [K-components, clusters, and slic-ings in graphs, SI AM J. Appl. Math. 22 (1972), pp. 459-480] proved two minimax theorems related to δ(G) and k'(G), and obtained polynomial algorithms to determine δ(G), k'(G) and k(G). The restricted edge-connectivity of G, denoted by λ_2(G), is the minimum size of a restricted edge-cut of G. We define λ_2(G) = max{λ_2(H) :H is contained in G). For a digraph D, let k (D), λ(D), δ~-(D) and δ~+(D) denote the strong connectivity, arc-strong connectivity, minimum in-degree and out-degree of D, respectively. For each f_∈ {k,λ,δ~-,δ~+},define f(D) = max{f(H) : Hisasubdigraph of D}.Inthispaper, we obtain analogous minmax duality results, which are applied to yield polynomial algorithms to determine δ~+ (D), δ~- (D), λ(D) and k(D) for a digraph D and λ_2(G) for a graph G.