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

摘要

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