Vertex deletion and cycles in multipartite tournaments Original Research Article

A tournament is an orientation of a complete graph and a multipartite tournament is an orientation of a complete multipartite graph. Therefore, a tournament is a k-partite tournament with exactly k-vertices. From the well-known theorem of Moon that every vertex of a strong tournament T is contained in a directed cycle of length m for 3 ⩽ m ⩽|V(T), it follows easily that T has at least two vertices u1 and u2 such that T − ui is strong for i = 1, 2, if |V(T)| ⩾ 4. As a generalization of this statement, we prove in this paper that all strongly connected multipartite tournaments D of order |V(D)|⩾ 4 have two different vertices u1 and u2 such that D − u1 is strong for i = 1, 2, with exception of a well determined family of bipartite tournaments and three well determined families of 3-partite tournaments. In addition, we show that the special class of Hamiltonian k-partite tournaments D of order n ⩾ 5 that are not 2-connected, contains a directed cycle C of length p or p − 1 for every 4 ⩽ p ⩽ n such that the induced subdigraph D[V(C)] is not 2-connected. Furthermore, every vertex of such a digraph is contained in a cycle of length n − 1 or n − 2.