کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648561 1632439 2010 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the number of non-critical vertices in strong tournaments of order NN with minimum out-degree δ+δ+ and in-degree δ−δ−
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the number of non-critical vertices in strong tournaments of order NN with minimum out-degree δ+δ+ and in-degree δ−δ−
چکیده انگلیسی

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{δ+,δ−}.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 6–7, 6 April 2010, Pages 1177–1183
نویسندگان
,