Weakly Complementary Cycles in 3-Connected Multipartite Tournaments
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
The vertex set of a digraph D is denoted by V (D). A c-partite tournament is an orientation of a complete c-partite graph. A digraph D is called cycle complementary if there exist two vertex disjoint cycles C₁ and C₂ such that V (D) = V (C₁) ∪ V (C₂), and a multipartite tournament D is called weakly cycle complementary if there exist two vertex disjoint cycles C₁ and C₂ such that V (C₁) ∪ V (C₂) contains vertices of all partite sets of D. The problem of complementary cycles in 2-connected tournaments was completely solved by Reid [4] in 1985 and Z. Song [5] in 1993. They proved that every 2-connected tournament T on at least 8 vertices has complementary cycles of length t and │V(T)│ ¡ t for all 3 ≤ t ≤ │V(T)│/2. Recently, Volkmann [8] proved that each regular multipartite tournament D of order │V (D)│ ≥ 8 is cycle complementary. In this article, we analyze multipartite tournaments that are weakly cycle complementary. Especially, we will characterize all 3-connected c-partite tournaments with c ≥ 3 that are weakly cycle complementary.
Abstract
The vertex set of a digraph D is denoted by V (D). A c-partite tournament is an orientation of a complete c-partite graph. A digraph D is called cycle complementary if there exist two vertex disjoint cycles C₁ and C₂ such that V (D) = V (C₁) ∪ V (C₂), and a multipartite tournament D is called weakly cycle complementary if there exist two vertex disjoint cycles C₁ and C₂ such that V (C₁) ∪ V (C₂) contains vertices of all partite sets of D. The problem of complementary cycles in 2-connected tournaments was completely solved by Reid [4] in 1985 and Z. Song [5] in 1993. They proved that every 2-connected tournament T on at least 8 vertices has complementary cycles of length t and │V(T)│ ¡ t for all 3 ≤ t ≤ │V(T)│/2. Recently, Volkmann [8] proved that each regular multipartite tournament D of order │V (D)│ ≥ 8 is cycle complementary. In this article, we analyze multipartite tournaments that are weakly cycle complementary. Especially, we will characterize all 3-connected c-partite tournaments with c ≥ 3 that are weakly cycle complementary.
참고문헌 (11)
- J. A. Bondy, "Disconnected orientation and a conjecture of Las Vergnas", J. London Math. Soc, 14, pp.277~282 (1976)
- W. D. Goddard, "On the cycle structure of multipartite tour-naments, in:", pp.525~533 (1991), Graph Theory Combinat. Appl., 1, Wiley Interscience, New York
- T. Korneffel, "Complementary cycles in regular multipartite tournaments", where one cycle has length five, submitted
- K. B. Reid, "Two complementary circuits in two-connected tournaments", Ann. Discrete Math, 27, pp.321~334 (1985)
- Z. Song, "Complementary cycles of all length in tournaments", J. Combin. Theory Ser. B, 57, pp.18~25 (1993)
- M. Tewes, "Vertex deletion and cycles in multipartite tournaments", Discrete Math, 197-198, pp.769~779 (1999)
- L. Volkmann, "Cycles in multipartite tournaments: results and problems", Discrete Math, 245, pp.19~53 (2002)
- L. Volkmann, "All regular multipartite tournaments that are cycle complementary", Discrete Math, 281, pp.255~266 (2004)
- Lutz Volkmann, "Complementary Cycles in Regular Multipartite Tournaments, Where One Cycle Has Length Four", Kyungpook Mathematical Journal, 44(2), pp.219~247 (2004), 경북대학교 자연과학대학 수학과
- L. Volkmann, "Complementary cycles in regular multipartite tournaments", Australas. J. Combin, 31, pp.119~134 (2005)
- A. Yeo, "Diregular c-partite tournaments are vertex-pancyclic when c≥5", J. Graph theory, 32, pp.137~152 (1999)