Quadratic additive bound conjecture for sparse spanning strongly connected subgraphs of tournaments

Let kk be a positive integer, and let TT be a strongly kk-connected tournament on nn vertices. A strongly kk-connected spanning subgraph is a spanning subgraph with strong vertex-connectivity at least kk. Quadratic additive bound conjecture. There is a constant C>0C>0 such that TT contains a strongly kk-connected spanning subgraph DD with at most

kn+Ck2kn+Ck^2

arcs. The paper proves an upper bound of kn+750k2log2(k+1)kn+750k^2\log_2(k+1) arcs and states that reducing the additive term to O(k2)O(k^2) is conjectured; the supplied text gives no resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Dong Yeap Kang, Jaehoon Kim, Younjin Kim and Geewon Suh, “Sparse spanning k-connected subgraphs in tournaments”, arXiv:1603.02474 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.