کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651180 1342524 2006 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Longest cycles in almost regular 3-partite tournaments
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Longest cycles in almost regular 3-partite tournaments
چکیده انگلیسی

If DD is a digraph, then we denote by V(D)V(D) its vertex set. A multipartite or cc-partite tournament is an orientation of a complete cc-partite graph. The global irregularity of a digraph DD is defined byig(D)=max{max(d+(x),d-(x))-min(d+(y),d-(y))|x,y∈V(D)}.If ig(D)=0ig(D)=0, then DD is regular  , and if ig(D)⩽1ig(D)⩽1, then DD is called almost regular. In 1997, Yeo has shown that each regular multipartite tournament is Hamiltonian. This remains valid for almost all almost regular cc-partite tournaments with c≥4c≥4. However, there exist infinite families of almost regular 3-partite tournaments without any Hamiltonian cycle. In this paper we will prove that every vertex of an almost regular 3-partite tournament DD is contained in a directed cycle of length at least |V(D)|-2|V(D)|-2. Examples will show that this result is best possible.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 22, 28 November 2006, Pages 2931–2942
نویسندگان
,