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

✍ Scribed by Jørgen Bang-Jensen; Jing Huang; Anders Yeo

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 167 KB
• Volume: 46
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20004

✦ Synopsis

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