Complementary Cycles in Irregular Multipartite Tournaments

Abstract EN

A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph.

A digraph D is cycle complementary if there exist two vertex disjoint cycles C and C ′ such that V ( D ) = V ( C ) ∪ V ( C ′ ) .

Let D be a locally almost regular c -partite tournament with c ≥ 3 and | γ ( D ) | ≤ 3 such that all partite sets have the same cardinality r , and let C 3 be a 3 -cycle of D .

In this paper, we prove that if D - V ( C 3 ) has no cycle factor, then D contains a pair of disjoint cycles of length 3 and | V ( D ) | - 3 , unless D is isomorphic to T 7 , D 4,2 , D 4,2 ⁎ , or D 3,2 .