Article ID Journal Published Year Pages File Type
421133 Discrete Applied Mathematics 2015 5 Pages PDF
Abstract

A cc-partite tournament is an orientation of a complete cc-partite graph. Recently, M. Lu, et al., introduced the concept of quasi-Hamiltonian cycles, that is to say, cycles containing vertices from each partite set, in multipartite tournaments. W.D. Goddard and O.R. Oellermann established that every strong multipartite tournament contains a quasi-Hamiltonian cycle.In this paper, we show that every kk-strong (or kk-arc-strong) multipartite tournament contains at least kk quasi-Hamiltonian cycles. To that end, we prove the following stronger result: Every strong multipartite tournament contains a vertex whose all out-arcs are contained in a quasi-Hamiltonian cycle. Our results include and extend corresponding ones concerning tournaments due to C. Thomassen, as well as M. Goldberg and J.W. Moon.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,