X-最长圈的下界估计

An Improvement of the Lower Bound of X--longest Cycle

设G是连通图 ,X V(G) ,G[X]是G的X生成子图 .记σk(X) =min{ ∑ki =1d(vi) :{v1,v2 ,… ,vk}是G[X]的顶点独立集 } ,得到如下结果 :对于n阶的 1-坚韧图 (n≥ 3) ,X V(G) ,且σ3 (X) ≥n +r≥n ,3｜X｜- 2n≥ 8t- 6r- 17,则存在一个圈C满足｜C(X) ｜≥ { ｜X｜ ,｜N(It) ∩X｜+｜N(It) ∩V(C)｜} ,其中It 是X中t个顶点的独立集 .

For a graph G and XV(G), let G[X] be the subgraph of G induced by X and r an integer.We define the parameters σ k(X)= min ｛∑ki=1d(v i):{v 1,v 2,…,v k} is an independent set of G[X]}.It is shown that every 1-tough graph G of order n≥3,XV(G), and σ 3(X)≥n+r≥n, with 3|X|-2n≥8t-6r-17,has a cycle C satisfying |C(X)|≥{|X|,|N(I t)∩X|+|N(I t)∩V(C)|},where It is an independent set of t vertices in X .