Spanning k-arc-strong subdigraphs with few arcs in k-arc-strong tournaments

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 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 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 arcs. As our main result we prove that every k-arc-strong tournament contains a spanning k-arc-strong subdigraph with no more than 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.