k-连通无爪图中最长的圈

本文所涉及的图都是有限无向的简单图。设G是一个图,总用V(G)、E(G)分别表示G的顶点集、边集,而p=|V(G)|。设,总用G[U]表示G中由U导出的子图。图G称为无爪的,如果对于任意,总有。图G称为m一路连通,如果对于任意,总有长至少为m的(u,v)一路。除此,本文所用的术语和记号可参见[1]。