Longest paths in strong spanning oriented subgraphs of strong semicomplete multipartite digraphs

Abstract

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. Volkmann (Manuscript, RWTH Aachen, Germany, June 1998) raised the following question: Let D be a strong semicomplete multipartite digraph with a longest path of length l. Does there exist a strong spanning oriented subgraph of D with a longest path of length l? We provide examples which show that the answer to this question is negative. We also demonstrate that every strong semicomplete multipartite digraph D, which is not bipartite with a partite set of cardinality one, has a strong spanning oriented subgraph of D with a longest path of length at least l−2. This bound is sharp.