×

Complementary cycles in irregular multipartite tournaments. (English) Zbl 1400.05099

Summary: 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) \cup V(C')\). Let \(D\) be a locally almost regular \(c\)-partite tournament with \(c \geq 3\) and \(| \gamma(D) | \leq 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}^\ast\), or \(D_{3,2}\).

MSC:

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

References:

[1] Reid, K. B., Two complementary circuits in two-connected tournaments, Annals of Discrete Mathematics, 27, 321-334, (1985) · Zbl 0573.05031
[2] Song, Z. M., Complementary cycles of all lengths in tournaments, Journal of Combinatorial Theory B, 57, 1, 18-25, (1993) · Zbl 0723.05062 · doi:10.1006/jctb.1993.1002
[3] Yeo, A., Diregular c-partite tournaments are vertex-pancyclic when \(c \geq 5\), Journal of Graph Theory, 32, 2, 137-152, (1999) · Zbl 0931.05037
[4] Volkmann, L., Complementary cycles in regular multipartite tournaments, The Australasian Journal of Combinatorics, 31, 119-134, (2005) · Zbl 1076.05042
[5] Volkmann, L., Complementary cycles in regular multipartite tournaments, where one cycle has length four, Kyungpook Mathematical Journal, 44, 2, 219-247, (2004) · Zbl 1063.05064
[6] He, Z.; Korneffel, T.; Meierling, D.; Volkmann, L.; Winzen, S., Complementary cycles in regular multipartite tournaments, where one cycle has length five, Discrete Mathematics, 309, 10, 3131-3149, (2009) · Zbl 1229.05170 · doi:10.1016/j.disc.2008.08.022
[7] Volkmann, L., Complementary cycles in almost regular multipartite tournaments, where one cycle has length four, Discrete Applied Mathematics, 161, 13-14, 2169-2177, (2013) · Zbl 1286.05058 · doi:10.1016/j.dam.2013.03.006
[8] Bai, Y.; Li, H.; He, W., Complementary cycles in regular bipartite tournaments, Discrete Mathematics, 333, 14-27, (2014) · Zbl 1298.05141 · doi:10.1016/j.disc.2014.06.008
[9] He, Z.; Volkmann, L.; Wang, Y., Complementary cycles in almost regular multipartite tournaments, Ars Combinatoria, 113A, 201-224, (2014) · Zbl 1324.05078
[10] Yeo, A., Semicomplete multipartite digraphs [Ph.D. thesis], (1998), Odense University · Zbl 0944.05053
[11] Bondy, J. A., Diconnected orientation and a conjecture of Las Vergnas, Journal London Mathematical Society, 14, 277-282, (1976) · Zbl 0344.05124
[12] Yeo, A., How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity?, Graphs and Combinatorics, 15, 4, 481-493, (1999) · Zbl 0939.05059 · doi:10.1007/s003730050080
[13] Tewes, M., Almost all regular c-partite tournaments with \(c \geq 5\) are vertex pancyclic, Discrete Mathematics, 242, 1–3, 201-228, (2002) · Zbl 0993.05083 · doi:10.1016/s0012-365x(01)00212-6
[14] Gutin, G.; Yeo, A., Note on the path covering number of a semicomplete multipartite digraph, Journal of Combinatorial Mathematics and Combinatorial Computing, 32, 231-237, (2000) · Zbl 0949.05066
[15] Volkmann, L.; Winzen, S., Almost regular multipartite tournaments containing a Hamiltonian path through a given arc, Discrete Mathematics, 285, 1–3, 267-278, (2004) · Zbl 1047.05021 · doi:10.1016/j.disc.2004.04.009
[16] Volkmann, L., Cycles in multipartite tournaments: results and problems, Discrete Mathematics, 245, 1–3, 19-53, (2002) · Zbl 0996.05063 · doi:10.1016/s0012-365x(01)00419-8
[17] Li, S.; Meng, W.; Guo, Y., Three supplements to Reid’s theorem in multipartite tournaments, Discrete Applied Mathematics, 158, 4, 340-348, (2010) · Zbl 1225.05117 · doi:10.1016/j.dam.2009.05.004
[18] Volkmann, L.; Winzen, S., Weakly complementary cycles in 3-connected multipartite tournaments, Kyungpook Mathematical Journal, 48, 2, 287-302, (2008) · Zbl 1158.05029 · doi:10.5666/kmj.2008.48.2.287
[19] He, Z.; Wang, Y., Weakly cycle complementary 3-partite tournaments, Graphs and Combinatorics, 27, 5, 669-683, (2011) · Zbl 1234.05114 · doi:10.1007/s00373-010-0993-y
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.