关于连通图最长圈的一个结果

A Note on the Circumference of Connected Graphs

设C是k-连通图G(2≤k≤6)的一个最长圈.H是G-C的一个分支.[5]中证明,若L(H)≥k-2,则C≥kδ-k(k-2),这里L(H)表示H中最长路的长度,δ表示G的最小度.本文在H满足特定的条件时,对于k∈{3,4,5}改进了上述C的度下界.

Let C be a Longest cycle in a k- connected graph G and let H be a component of G-C. In [5-], it was shown that ｜C｜≥kδ-k（k-2）,if L（H）≥k-2,where L（H） is the length of a longest path in H and δ is the minimum degree of G. In this paper, subject to some conditions on H, we improve the above lower bound of ｜C｜for k∈{3,4,5}.