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

Cycles and Paths Through Specified Vertices

作　　者：郑苏娟[1] 

机构地区：[1]河海大学数理系,南京210024

出　　处：《南京师大学报（自然科学版）》2000年第4期9-13,共5页Journal of Nanjing Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目

摘　　要：证明了下面两个结论 :(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} .Let G be a undirected finite simple graph, X a (k+1) independent set in G .Denote S i(X)=｛v∈V(G)N(ν)∩X=i)｝ and s i(X)=S i(X) for any i∈｛0,1,2,…,k+1｝ .In this paper,the following two conclusion was proved. (1)Let G be a k connected graph of order n,k≥2 , and S a subset of V(G) .If for any (k+1) independent set X is G[S] ,we have k+1i=1k+i-1ks i(X)>n-1then G contains a cycle through all vertices of S . (2)Let G be a (k+1) connected graph of order n,k≥2, and S a subset of V(G) .If for any (k+1) Independent set X in G[S] ,we havek+1i=1k+i-1ks i(X)>n,then G contains a (u,v )?path through all vertices of S for each pair ｛u,v｝V(G) .

关 键 词：HAMILTON图 HAmilton连通 S-极大圈 S-路 顶点集 

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