Sparse spanning k-connected subgraphs in tournaments
classification
🧮 math.CO
keywords
connectedstronglyspanningarcscontainseverysubgraphtournament
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.