کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651180 | 1342524 | 2006 | 12 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 306, Issue 22, 28 November 2006, Pages 2931–2942