Spanning k ‐arc‐strong subdigraphs with few arcs in k ‐arc‐strong tournaments
Jørgen Bang‐Jensen, Jing Huang, Anders Yeo · Journal of Graph Theory · 2004
Abstract Given a k ‐arc‐strong tournament T , we estimate the minimum number of arcs possible in a k ‐arc‐strong spanning subdigraph of T . We give a construction which shows that for each k ≥ 2, there are tournaments T on n vertices such that every k ‐arc‐strong spanning subdigraph of T contains at least $nk + {k(k-1)\over 2}$ arcs. In fact, the tournaments in our construction have the property that every spanning subdigraph with minimum in‐ and out‐degree at least k has $nk + {k(k-1)\over 2}$ arcs. This is best possible since it can be shown that every k ‐arc‐strong tournament contains a spanning subdigraph with minimum in‐ and out‐degree at least k and no more than $nk + {k(k-1)\over 2}$ arcs. As our main result we prove that every k ‐arc‐strong tournament contains a spanning k ‐arc‐strong subdigraph with no more than $nk + 136k^2$ arcs. We conjecture that for every k ‐arc‐strong tournament T , the minimum number of arcs in a k ‐arc‐strong spanning subdigraph of T is equal to the minimum number of arcs in a spanning subdigraph of T with the property that every vertex has in‐ and out‐degree at least k . We also discuss the implications of our results on related problems and conjectures. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 265–284, 2004