Sparse highly connected spanning subgraphs in dense directed graphs

Abstract

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 the equality holds for the complete bipartite digraph ${DK}_{k,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+\overline{\Delta }(D))$ edges, where $\overline{\Delta }(D)$ denotes the maximum degree of the complement of the underlying undirected graph of a digraph $D$. Here, the additional term $800k(k+\overline{\Delta }(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$. We also prove an analogous result for strongly $k$-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.

31 pages

References in corpus (3)

• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Sparse spanning $k$-connected subgraphs in tournaments

Cited by in corpus (1)

• On 1-factors with prescribed lengths in tournaments