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 greater than or equal to 2, there are to...
详细信息
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 greater than or equal to 2, there are tournaments Ton n vertices such that every k-arc-strong spanning subdigraph of T contains at least nk + (k(k-1))/(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))/(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))/(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. (C) 2004 Wiley Periodicals, Inc.
暂无评论