کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648561 | 1632439 | 2010 | 7 صفحه PDF | دانلود رایگان |

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{δ+,δ−}.
Journal: Discrete Mathematics - Volume 310, Issues 6–7, 6 April 2010, Pages 1177–1183