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. 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received: October 26, 1998¶Final version received: August 16, 1999
Rights and permissions
About this article
Cite this article
Gutin, G., Yeo, A. Solution of a Conjecture of Volkmann on the Number of Vertices in Longest Paths and Cycles of Strong Semicomplete Multipartite Digraphs. Graphs Comb 17, 473–477 (2001). https://doi.org/10.1007/s003730170022
Issue Date:
DOI: https://doi.org/10.1007/s003730170022