南京师大学报（自然科学版）
南京師大學報（自然科學版）
남경사대학보（자연과학판）
JOURNAL OF NANJING NORMAL UNIVERSITY (NATURAL SCIENCE EDITION)
2000年
4期
9-13
,共5页
Hamilton图%Hamilton连通%S-极大圈
Hamilton圖%Hamilton連通%S-極大圈
Hamilton도%Hamilton련통%S-겁대권
证明了下面两个结论:(1)设G是k-连通的n阶图,k≥2,S V(G).若对G[S]的任意(k+1)-独立集X,有k+1∑i＝1(k+i-1)/(k)si(X)＞n-1,则G中有含S的全部顶点的圈;(2)设G是(k+1)-连通的n阶图,k≥2,S(U)V(G).若对G[S]的任意(k+1)-独立集X,有k+1∑i＝1(k+i-1)/(k)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}.
證明瞭下麵兩箇結論:(1)設G是k-連通的n階圖,k≥2,S V(G).若對G[S]的任意(k+1)-獨立集X,有k+1∑i＝1(k+i-1)/(k)si(X)＞n-1,則G中有含S的全部頂點的圈;(2)設G是(k+1)-連通的n階圖,k≥2,S(U)V(G).若對G[S]的任意(k+1)-獨立集X,有k+1∑i＝1(k+i-1)/(k)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}.
증명료하면량개결론:(1)설G시k-련통적n계도,k≥2,S V(G).약대G[S]적임의(k+1)-독립집X,유k+1∑i＝1(k+i-1)/(k)si(X)＞n-1,칙G중유함S적전부정점적권;(2)설G시(k+1)-련통적n계도,k≥2,S(U)V(G).약대G[S]적임의(k+1)-독립집X,유k+1∑i＝1(k+i-1)/(k)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}.
