有向图中弧数和最长回路

摘要

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