Article ID Journal Published Year Pages File Type
4648561 Discrete Mathematics 2010 7 Pages PDF
Abstract

Let TT be a strong tournament of order n≥4n≥4 with given minimum out-degree δ+δ+ and in-degree δ−δ−. By definition, a vertex ww in TT is non-critical if the subtournament T−wT−w is also strong. In the present paper, we show that TT contains at least min{n,2δ++2δ−−2}min{n,2δ++2δ−−2} non-critical vertices, and all tournaments for which this lower bound is attained are determined. For the case min{δ+,δ−}≥2min{δ+,δ−}≥2, we also describe all strong tournaments of order n≥2δ++2δ−n≥2δ++2δ− that include exactly 2δ++2δ−−12δ++2δ−−1 non-critical vertices. From this description it follows that any strong tournament TT of order n≥2δ++2δ−+2n≥2δ++2δ−+2 with min{δ+,δ−}≥2min{δ+,δ−}≥2 contains at least 2δ++2δ−2δ++2δ− non-critical vertices. Finally, for the case min{δ+,δ−}≥4min{δ+,δ−}≥4, we completely describe all strong tournaments of order n≥2δ++2δ−+2n≥2δ++2δ−+2 that admit exactly 2δ++2δ−2δ++2δ− non-critical vertices. All of these results sharpen those obtained recently by K. Kotani in terms of δ=min{δ+,δ−}δ=min{δ+,δ−}.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,