Componentwise Complementary Cycles in Multipartite Tournaments

The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n 〉 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Le...

Full description

Saved in:
Bibliographic Details
Published in:Acta Mathematicae Applicatae Sinica 2012, Vol.28 (1), p.201-208
Main Authors: He, Zhi-hong, Li, Guo-jun, Zhou, Xue-qin
Format: Article
Language:English
Subjects:
Applications of Mathematics
Math Applications in Computer Science
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
互补
循环
有向图
比赛
非周期性
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n 〉 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Let D be a 2-strong n-partite （n 〉 6） tournament that is not a tournament. Let C be a 3-cycle of D and D ／ V（C） be nonstrong. For the unique acyclic sequence D1, D2,..., Da of D ／ V（C）, where a 〉 2, let Dc = {Di｜Di contains cycles, i = 1,2,...,a}, Dc = {D1,D2,...,Da} ／ De. If Dc≠ 0, then D contains a pair of componentwise complementary cycles.
ISSN:0168-9673
1618-3932
DOI:10.1007/s10255-012-0135-9