二部竞赛图中的AD路与AD回路

ANTIDIRECTED CYCLES AND PATHS IN BIPARTITE TOURNAMENTS

本文证明了：若对二部竞赛图Ｔ的每一顶点ｖ，总有ｍｉｎ｛ｄ＿Ｔ￣－（ｖ），ｄ＿￣－（ｖ）｝≥ｋ≥３，则Ｔ中存在长度至少为４ｋ的ＡＤ路或ＡＤ回路，除非Ｔ同构于一类例外图之一。作为推论，我们得到：正则二部竞赛图Ｔ含有ＡＤＨ回路，除非Ｔ属于一类例外图。

Let T be a bipartite tournament.This paper shows that if for each vertex v in T,then T contains either an antidirected cycle or an antidirected path of length at least 4k,except for a described case. As a corollary of this result, we obtain that every regular bipartite tournament contains an antidirected Hamilton cycle except for a described case.