×

All regular multipartite tournaments that are cycle complementary. (English) Zbl 1049.05043

A digraph \(D\) is cycle complementary if there are two disjoint cycles of \(D\) covering all vertices in \(D\). A complete \(c\)-partite tournament is an orientation of a complete \(c\)-partite graph. It is proved that, with two exceptions, every regular \(c\)-partite tournament (\(c\geq 3\)) of order at least 6 is cycle complementary.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2000), Springer: Springer London
[2] Bondy, J. A., Diconnected orientation and a conjecture of Las Vergnas, J. London Math. Soc., 14, 277-282 (1976) · Zbl 0344.05124
[3] Chen, G.; Gould, R. J.; Li, H., Partitioning vertices of a tournament into independent cycles, J. Combin. Theory Ser. B, 83, 213-220 (2001) · Zbl 1028.05038
[4] Y. Guo, Semicomplete multipartite digraphs: a generalization of tournaments, Habilitation Thesis, RWTH Aachen, 1998, 102pp.; Y. Guo, Semicomplete multipartite digraphs: a generalization of tournaments, Habilitation Thesis, RWTH Aachen, 1998, 102pp.
[5] Guo, Y.; Volkmann, L., On complementary cycles in locally semicomplete digraphs, Discrete Math., 135, 121-127 (1994) · Zbl 0816.05036
[6] Guo, Y.; Volkmann, L., Locally semicomplete digraphs that are complementary m-pancyclic, J. Graph Theory, 21, 121-136 (1996) · Zbl 0845.05048
[7] Gutin, G., Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey, J. Graph Theory, 19, 481-505 (1995) · Zbl 0839.05043
[8] Gutin, G.; Yeo, A., Note on the path covering number of a semicomplete multipartite digraph, J. Combin. Math. Combin. Comput., 32, 231-237 (2000) · Zbl 0949.05066
[9] Reid, K. B., Two complementary circuits in two-connected tournaments, Ann. Discrete Math., 27, 321-334 (1985) · Zbl 0573.05031
[10] Reid, K. B., Three problems on tournament, graph theory and its applications: east and west, Ann. New York Acad. Sci., 576, 466-473 (1989)
[11] Song, Z., Complementary cycles in bipartite tournaments, J. Nanjing Inst. Technol., 18, 32-38 (1988)
[12] Song, Z., Complementary cycles of all lengths in tournaments, J. Combin. Theory Ser. B, 57, 18-25 (1993) · Zbl 0723.05062
[13] Turán, P., An extremal problem in graph theory, Mat.-Fiz. Lapok, 48, 436-452 (1941), (in Hungarian)
[14] Volkmann, L., Cycles in multipartite tournaments: results and problems, Discrete Math., 245, 19-53 (2002) · Zbl 0996.05063
[15] L. Volkmann, Complementary cycles in regular multipartite tournaments, manuscript (2002), submitted for publication.; L. Volkmann, Complementary cycles in regular multipartite tournaments, manuscript (2002), submitted for publication.
[16] Yeo, A., One-diregular subgraphs in semicomplete multipartite digraphs, J. Graph Theory, 24, 175-185 (1997) · Zbl 0865.05045
[17] A. Yeo, Semicomplete multipartite digraphs, Ph.D. Thesis, Odense University, 1998.; A. Yeo, Semicomplete multipartite digraphs, Ph.D. Thesis, Odense University, 1998. · Zbl 0944.05053
[18] Yeo, A., How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity?, Graphs Combin., 15, 481-493 (1999) · Zbl 0939.05059
[19] K. Zhang, Z. Song, Complementary cycles containing a pair of fixed vertices in bipartite tournaments, Appl. Math., J. Chin. Univ. 3 (3) 1988 401-407 (in chinese, with English summary).; K. Zhang, Z. Song, Complementary cycles containing a pair of fixed vertices in bipartite tournaments, Appl. Math., J. Chin. Univ. 3 (3) 1988 401-407 (in chinese, with English summary). · Zbl 0761.05061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.