کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419706 683851 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
kk-strong spanning local tournaments in locally semicomplete digraphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
kk-strong spanning local tournaments in locally semicomplete digraphs
چکیده انگلیسی

We point out mistakes in two papers previously published in Discrete Applied Mathematics, dealing with highly strongly connected spanning local tournaments in locally semicomplete digraphs. We conjecture that every (2k−1)(2k−1)-strong locally semicomplete digraph on at least 2k+12k+1 vertices contains a kk-strong spanning local tournament and prove the conjecture for k=1,2k=1,2. We also prove that every 5-strong locally semicomplete digraph which is not semicomplete contains a 3-strong spanning local tournament. We furthermore show that for semicomplete digraphs, which form a proper subclass of locally semicomplete digraphs, 2k−12k−1 would be the best possible bound and for locally semicomplete digraphs which are not semicomplete we show that the correct bound is at least 2k−32k−3.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 11, 6 June 2009, Pages 2536–2540
نویسندگان
,