X-最长圈的下界估计  

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

作　　者：罗红[1] 梁立[2] 

机构地区：[1]云南大学成人教育学院,云南昆明650091 [2]云南师范大学计算机系,云南昆明650092

出　　处：《云南大学学报（自然科学版）》2000年第3期169-171,共3页Journal of Yunnan University(Natural Sciences Edition)

基　　金：云南省教委自然科学基金资助项目!( 964 10 91)

摘　　要：设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 .

关 键 词：1-坚韧图 X-最长圈 X-控制圈 连通图 下界 估计 

分 类 号：O157.5[理学—数学]