pith. sign in

arxiv: 1603.02474 · v2 · pith:7D54O2UMnew · submitted 2016-03-08 · 🧮 math.CO

Sparse spanning k-connected subgraphs in tournaments

classification 🧮 math.CO
keywords connectedstronglyspanningarcscontainseverysubgraphtournament
0
0 comments X
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.