1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 Department of Mathematics and Statistics, Brunel, The University of West London3 Department of Mathematics and Statistics, University of Victoria,
A digraph obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete multipartite digraph. L. Volkmann conjectured that l≤2c−1, where l (c, respectively) is the number of vertices in a longest path (longest cycle) of a strong semicomplete multipartite digraph. The bound on l is sharp. We settle this conjecture in affirmative.
Graphs and Combinatorics, 2001, Vol 17, Issue 3, p. 473-477