The ratio of the longest cycle and longest path in semicomplete multipartite digraphs (Q5937609): Difference between revisions

A digraph \(D\) obtained by replacing each edge of a complete multipartite graph by an arc or a pair of mutually opposite acrs is called a complete multipartite digraph. For a complete multipartite digraph \(D\), let \(p,c,\alpha,k\) denote the number of vertices in a longest path, the number of vertices in a longest cycle, the independence number, and the strong connectivity, respectively. (For undefined terms on digraphs, see \textit{J. Bang-Jensen} and \textit{G. Gutin} [Digraphs. Theory, algorithms and applications (Springer Monographs in Mathematics. London: Springer) (2000)].) Volkmann conjectured that \(c\geq k(p+1)/(k+1)\) for every strongly connected semicomplete digraph \(D.\) Recently, Gutin and Yeo proved that this conjecture holds for \(k=1\). The authors of this paper show that the conjecture holds if \(k=\alpha - 1.\)