计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (17): 7-.

• 博士论坛 • 上一篇    下一篇

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

何志红,李国君   

  1. 山东大学
  • 收稿日期:2006-03-10 修回日期:1900-01-01 出版日期:2006-06-11 发布日期:2006-06-11
  • 通讯作者: 何志红 zhihhe

Componentwise Complementary Cycles in Diregular Multipartite Tournaments

,   

  1. 山东大学
  • Received:2006-03-10 Revised:1900-01-01 Online:2006-06-11 Published:2006-06-11

摘要: 竞赛图的共轭圈问题已经完全解决, 而关于多部有向图的共轭圈问题仍然是一个open问题。 Yeo于1999年提出正则多部竞赛图包含共轭圈的猜想。本文根据分量共轭圈(componentwise complementary cycles)的定义, 证明了:如果D是一个正则的n-部竞赛图 ( ),则D包含一对分量共轭圈C1和C2,除非它同构于T71。 这对于解决Yeo的猜想和多部有向图的共轭圈问题有一定的意义。

Abstract: The problem of complementary cycles in tournaments was 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 get the following result. If D is a diregular n-partite ( ) tournament, then it contains a pair of componentwise complementary cycles C1 and C2, unless it is isomorphic to T71. This result gives impetus to resolving Yeo's conjecture and the problem of complementary cycles in multipartite digraph.