Solution of a Conjecture of Volkmann on the Number of Vertices in Longest Paths and Cycles of Strong Semicomplete Multipartite Digraphs |
| |
| Authors: | Gregory Gutin Anders Yeo |
| |
| Institution: | (1) Department of Mathematics and Statistics, Brunel, The University of West London, Uxbridge, Middlesex, UB8 3PH, UK. e-mail: z.g.gutin@brunel.ac.uk, GB;(2) Department of Mathematics and Statistics, University of Victoria, P.O. Box 3045, Victoria B.C., Canada V8W 3P4. e-mail: yeo@Math.UVic.ca, CA |
| |
| 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.
Received: October 26, 1998?Final version received: August 16, 1999 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
