Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs

摘要

Mader proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k(2) edges, where equality holds for the complete bipartite digraph DKk,n-k. For dense strongly k-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly k-connected n-vertex digraph D contains a strongly k-connected spanning subgraph with at most kn + 800k(k + ((Delta) over bar (D))) edges, where ((Delta) over bar (D)) denotes the maximum degree of the complement of the underlying undirected graph of a digraph D. Here, the additional term 800k(k + ((Delta) over bar (D))) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k(2) edges, which is essentially optimal since 800k(2) cannot be reduced to the number less than k(k - 1)/2.