One-diregular subgraphs in semicomplete multipartite digraphs

The problem of finding necessary and sufficient conditions for a semicomplete multipartite digraph (SMD) to be Hamiltonian, seems to be both very interesting and difficult. Bang-Jensen, Gutin and Huang ( Discrete Math to appear) proved a sufficient condition for a SMD to be Hamiltonian. A strengthening of this condition, shown in this paper, allows us to prove the following three results. We prove that every k-strong SMD with at most k-vertices in each color class is Hamiltonian and every k-strong SMD has a cycle through any set of k vertices. These two statements were stated as conjectures by Volkmann (L. Volkmann, a talk at the second Krakw Conference of Graph Theory (1994)) and Bang-Jensen, Gutin, and Yeo (J. Bang-Jensen, G. Gutin, and A. Yeo, On k-strong and k-cyclic digraphs, submitted), respectively. We also prove that every diregular SMD is Hamiltonian, which was conjectured in a weaker form by Zhang (C.-Q. Zhang, Hamilton paths in multipartite oriented graphs, Ann Discrete Math. 41 (1989), 499–581). © 1997 John Wiley & Sons, Inc.