正则多部竞赛图中的分量共轭圈  

Componentwise Complementary Cycles in Diregular Multipartite Tournaments

作　　者：何志红[1] 李国君[1] 

机构地区：[1]山东大学数学与系统科学学院,济南250100

出　　处：《计算机工程与应用》2006年第17期7-8,共2页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(编号:60373025)

摘　　要：竞赛图的共轭圈问题已经完全解决,而关于多部有向图的共轭圈问题仍然是一个open问题。Yeo于1999年提出正则多部竞赛图包含共轭圈的猜想。论文根据分量共轭圈(componentwisecomplementarycycles)的定义,证明了:如果D是一个正则的n-部竞赛图(n≥4),则D包含一对分量共轭圈C1和C2,除非它同构于T71。这对于解决Yeo的猜想和多部有向图的共轭圈问题有一定的意义。The problem of complementary cycles in tournaments has been completely solved.However,for semicomplete multi-partite digraphs,the problem of complementary cycles is still open.In 1999,Yeo presented conjecture which a diregular multipartite tournament has a pair of complementary cycles.In this paper,based on the definition of componentwise complementary cycles,we have gotten the following result.lf D is a diregular n-partite（n≥4） tournament,then it contains a pair of componentwise complementary cycles C1 and C2,unless it is isomorphic to T7^1 .This result gives impetus to resolving Yeo＇s conjecture and the problem of complementary cycles in multipartite digraph.

关 键 词：分量共轭圈 正则的 多部竞赛图 

分 类 号：O157.5[理学—数学]