Longest paths through an arc in strong semicomplete multipartite digraphs

A digraph obtained by replacing each edge of a complete n-partite graph by an arc or a pair of mutually opposite arcs is called a semicomplete n-partite digraph. An n-partite tournament is an orientation of a complete n-partite graph. If D is a strongly connected semicomplete n-partite digraph, then we prove that every arc of D which belongs to a directed cycle of length at least 3, is contained in a directed path of order ⌈(n+3)/2⌉. Consequently, every arc of a strongly connected n-partite tournament is contained in a directed path with ⌈(n+3)/2⌉ vertices. This bound is new even for tournaments. If in addition, every partite set consists of at least two vertices, then we even have the slightly better lower bound ⌈(n+5)/2⌉. Various families of examples will show that these results are best possible.