正则4-部竞赛图泛圈的一个充分条件

A Sufficient Condition for a Regular 4-Partite Tournament to be Pancyclic

研究了正则4-部竞赛图的泛圈性问题.将找原图中某一长度的圈归结为找某个子图的哈密尔顿圈,利用有向图的哈密尔顿圈理论,并结合有向图中圈可归约的概念及性质,给出了正则4-部竞赛图泛圈的一个充分条件,得出了:设D是一个正则4-部竞赛图,V1,V2,V3,V4是D的部集且︱Vi︱=vD*≥8(i=1,2,3,4),如果对每个1≤i≤4来说,Vi-1控制Vi中至少「VD*/4(V0=V4)个顶点,则D是泛圈的.

The pancyclicity of regular 4-partite tournaments was investigated. To seek for a cycle with certain length in original-digraph was reduced to find a Hamilton cycle of some sub-digraph. Using Hamilton theories of digraphs and combining the notion and properties of reduction, a sufficient condition for a regular 4-partite tournament to be pancyclic was obtained and the following result is proved： Let D be a regular 4-partite tour- nament with partite sets V1,Vz,V3,V4 and ｜Vi｜ = v;） ≥8（i = 1,2,3,4）. If Vi-1 dominates at least 4-VD＊ vertices in Vi（1≤i≤4, V0=V4）, then D is pancyclic.