Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
multipartite tournaments; regular multipartite tournaments; cycles
multipartite tournaments; regular multipartite tournaments; cycles
Summary:
If $x$ is a vertex of a digraph $D$, then we denote by $d^+(x)$ and $d^-(x)$ the outdegree and the indegree of $x$, respectively. A digraph $D$ is called regular, if there is a number $p \in \mathbb{N}$ such that $d^+(x) = d^-(x) = p$ for all vertices $x$ of $D$. A $c$-partite tournament is an orientation of a complete $c$-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether $c$-partite tournaments with $r$ vertices in each partite set contain a cycle with exactly $r-1$ vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if $c = 2$. If $c \ge 3$, then we will show that a regular $c$-partite tournament with $r \ge 2$ vertices in each partite set contains a cycle with exactly $r-1$ vertices from each partite set, with the exception of the case that $c = 4$ and $r = 2$.
References:
[1] J. Bang-Jensen, G. Gutin: Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2000. MR 2472389
[2] L. W. Beineke, C. Little: Cycles in bipartite tournaments. J. Combinat. Theory Ser. B 32 (1982), 140–145. DOI 10.1016/0095-8956(82)90029-6 | MR 0657682
[3] J. A. Bondy: Diconnected orientations and a conjecture of Las Vergnas. J. London Math. Soc. 14 (1976), 277–282. MR 0450115 | Zbl 0344.05124
[4] P. Camion: Chemins et circuits hamiltoniens des graphes complets. C. R. Acad. Sci. Paris 249 (1959), 2151–2152. MR 0122735 | Zbl 0092.15801
[5] W. D. Goddard, O. R. Oellermann: On the cycle structure of multipartite tournaments. In: Graph Theory Combinat. Appl. 1, Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schenk (eds.), Wiley-Interscience, New York, 1991, pp. 525–533. MR 1170802
[6] Y. Guo: Semicomplete multipartite digraphs: a generalization of tournaments. Habilitation thesis, RWTH Aachen, 1998.
[7] G. Gutin: Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey. J. Graph Theory 19 (1995), 481–505. DOI 10.1002/jgt.3190190405 | MR 1333778 | Zbl 0839.05043
[8] G. Gutin, A. Yeo: Note on the path covering number of a semicomplete multipartite digraph. J. Combinat. Math. Combinat. Comput. 32 (2000), 231–237. MR 1748910
[9] J. W. Moon: On subtournaments of a tournament. Canad. Math. Bull. 9 (1966), 297–301. DOI 10.4153/CMB-1966-038-7 | MR 0200196 | Zbl 0141.41204
[10] L. Rédei: Ein kombinatorischer Satz. Acta Litt. Sci. Szeged 7 (1934), 39–43.
[11] M. Tewes, L. Volkmann, and A. Yeo: Almost all almost regular $c$-partite tournaments with $c \ge 5$ are vertex pancyclic. Discrete Math. 242 (2002), 201–228. DOI 10.1016/S0012-365X(01)00212-6 | MR 1874765
[12] L. Volkmann: Strong subtournaments of multipartite tournaments. Australas. J. Combin. 20 (1999), 189–196. MR 1723872 | Zbl 0935.05051
[13] L. Volkmann: Cycles in multipartite tournaments: results and problems. Discrete Math. 245 (2002), 19–53. MR 1887047 | Zbl 0996.05063
[14] L. Volkmann: All regular multipartite tournaments that are cycle complementary. Discrete Math. 281 (2004), 255–266. DOI 10.1016/j.disc.2003.09.012 | MR 2047772 | Zbl 1049.05043
[15] L. Volkmann, S. Winzen: Almost regular $c$-partite tournaments contain a strong subtournament of order $c$ when $c \ge 5$. Submitted.
[16] A. Yeo: One-diregular subgraphs in semicomplete multipartite digraphs. J. Graph Theory 24 (1997), 175–185. DOI 10.1002/(SICI)1097-0118(199702)24:2<175::AID-JGT5>3.0.CO;2-N | MR 1425821 | Zbl 0865.05045
[17] A. Yeo: Semicomplete multipartite digraphs. Ph.D. Thesis, Odense University, 1998. Zbl 0916.05049
[18] A. Yeo: How close to regular must a semicomplete multipartite digraph be to secure Hamiltonicity?. Graphs Combin. 15 (1999), 481–493. DOI 10.1007/s003730050080 | MR 1735094 | Zbl 0939.05059
[19] K.-M. Zhang: Vertex even-pancyclicity in bipartite tournaments. Nanjing Daxue Xuebao Shuxue Bannian Kan 1 (1984), 85–88. MR 0765176
Search
Partner of
