过特定顶点集的S-圈与S-路

摘要

证明了下面两个结论 :(1)设G是k-连通的n阶图 ,k≥ 2 ,S V(G) .若对G[S]的任意 (k+ 1) -独立集X ,有 k+1i=1k +i- 1k si(X)>n- 1,则G中有含S的全部顶点的圈 ;(2 )设G是 (k+ 1) -连通的n阶图 ,k ≥ 2 ,S V(G) .若对G[S]的任意 (k+ 1) -独立集X ,有 k+1i=1k+i - 1k si(X) >n ,则对任意的 {u ,v}≤V(G) ,G中有含S的全部顶点的 (u ,v) 路 .其中 ,G是有限无向简单图 .X为G的 (k+ 1) -独立集 ,Si(X) ={v∈V(G) N(v) ∩X =i} ,si(X)=si(x) ,i∈ { 0 ,1,2 ,… ,k + 1} .