Sparse spanning $k$-connected subgraphs in tournaments

Abstract

In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn+g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn+750k^2\log (k+1)$ arcs.

References in corpus (2)

• 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

Cited by in corpus (1)

• Sparse highly connected spanning subgraphs in dense directed graphs