The ratio of the longest cycle and longest path in 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. We call α(D) = max_1 ≤ i ≤ n{|V_i|} the independence number of the semicomplete n-partite digraph D, where V_1, V_2, …, V_n are the partite sets of D. Let p and c, respectively, denote the number of vertices in a longest directed path and the number of vertices in a longest directed cycle of a digraph D. Recently, Gutin and Yeo proved that c ≥ (p + 1)/2 for every strongly connected semicomplete n-partite digraph D. In this paper we present for the special class of semicomplete n-partite digraphs D with connectivity κ(D) = α(D) - 1 ≥ 1 the better bound c ≥ (κ(D)/κ(D) + 1)(p + 1). In addition, we present examples which show that this bound is best possible.