Gutin, Gregory, Bang-Jensen, J. and Huang, J. (1996) A sufficient condition for a semicomplete multipartite digraph to be Hamiltonian. Discrete Mathematics, 161
Full text access: Open
A multipartite tournament is an orientation of a complete k-partite graph for some k 2. A factor of a digraph D is a collection of vertex disjoint cycles covering all the vertices of D. We show that there is no degree of strong connectivity which together with the existence of a factor will guarantee that a multipartite tournament is Hamiltonian. Our main result is a sufficient condition for a multipartite tournament to be Hamiltonian. We show that this condition is general enough to provide easy proofs of many existing results on paths and cycles in multipartite tournaments. Using this condition, we obtain a best possible lower bound on the length of a longest cycle in any strongly connected multipartite tournament.
This is a Submitted version This version's date is: 1996 This item is not peer reviewed
https://repository.royalholloway.ac.uk/items/f77fd1f6-fb39-9409-1034-7161f0eb7900/6/
Deposited by Research Information System (atira) on 22-Jul-2014 in Royal Holloway Research Online.Last modified on 22-Jul-2014