-
题名过特定顶点集的S-圈与S-路
- 1
-
-
作者
郑苏娟
-
机构
河海大学数理系
-
出处
《南京师大学报(自然科学版)》
CAS
CSCD
2000年第4期9-13,共5页
-
基金
国家自然科学基金资助项目
-
文摘
证明了下面两个结论 :(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} .
-
关键词
HAMILTON图
HAmilton连通
s-极大圈
s-路
顶点集
-
Keywords
Hamiltonian graph
Hamiltonian connected
S -maximal cycle
-
分类号
O157.5
[理学—基础数学]
-