2-连通图中X-最长圈下界估计 (2000年)

给一个图G,X∈V(G),G[X]为G的X生成子图,r为正整数。定义a(X)=max{|S|}S是G[X]的顶点独立集,ak(X)=min{∑d(vi)I{v1,v2…VK}是G[X]的顶点独立集,NCk(X)=minUk=i=1N(vi)|{v1,…,vk是G[x]的独点独立集(k>2).我们得到结论;对一任意的n阶2-连通图G(n>3),xSG,且Q3(X))n+r>n+2,则存在一个包含X的顶点数为min{|X|,|X|+NCr+2+e(n+r)(X)-a(X)的圈,s(i)=3[1/3i,]-1/