One-diregular subgraphs in semicomplete multipartite digraphs

✍ Scribed by Yeo, Anders

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 154 KB
• Volume: 24
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199702)24:2<175::aid-jgt5>3.0.co;2-n

✦ Synopsis

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.-