有向图中弧数和最长回路

Number of Arcs and Longest Gycles in Digraph

设 D 是阶为2r+3的强连通有向图,最小内次和外次至少 r(≥2).本文证明了:若 D 中至少含有3r^2+6r+3条弧,则 D 含有长至少2r+2的回路.这部分说明了 Heydemann 和 Sotteau 提出的一个猜测成立.

Let D be a strong digraph of order 2r+3 and the minimum indegree and outdegree at least r(≥2).The paper proves that,if D contains at least 3r^2+6r+3 arcs,then D contains a cycle of length at least 2r+2.This partia- lly shows that a conjecture proposed by Heydemann and Sotteau holds.