(k-1)连通无爪图中的最长路

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