Vertex deletion and cycles in multipartite tournaments (Q1292878): Difference between revisions

A \(k\)-partite tournament is an orientation of a complete \(k\)-partite graph. When \(k\) is not important, we speak about a multipartite tournament. In the special case when \(k= n\), the number of vertices, we obtain a tournament, i.e. an orientation of a complete graph. It is well known and easy to show that every strong tournament \(T\) contains two vertices \(x_1\), \(x_2\) such that \(T- x_i\) is strong for \(i= 1,2\). The authors show that this result extends to general multipartite tournaments, except for one family of 2-partite tournaments and three families of 3-partite tournaments. The paper also contains some results on cycles in Hamiltonian multipartite tournaments which are not 2-strong. In particular the result that for any such digraph on \(n\geq 5\) vertices, every vertex is on a cycle of length \(n-1\) or \(n-2\).