Cycles and Paths Through Specified Vertices
Zheng Yao Su · 2000
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-1then 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 havek+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) .