摘要
设 Ｇ 为ｎ 阶３连通无爪图，δ＝ ｍｉｎ｛ｄ（ ｘ）｜ ｘ ∈ Ｖ（ Ｇ）｝ ，δ＝ ｍｉｎ｛ ｍａｘ（ｄ（ ｘ） ，ｄ（ ｙ））｜ ｘ ，ｙ∈ Ｖ（ Ｇ） ，ｄ（ ｘ ，ｙ） ＝ ３｝ ，则 Ｃ（ Ｇ） ≥ｍｉｎ｛ ｎ ，３ δ＋ δ，６ δ｝·用反证法，若图 Ｇ 的最长圈不满足结论，利用 Ｇ 的３连通性和无爪性构造矛盾·
It was proved that if G is a 3 connected claw free graph on n vertices with the minimum degree δ =min{d( x )| x ∈ V(G )｝and δ *=min｛max(d( x ),d( y ))｜ x,y∈V(G) ,d( x,y )=3｝,then the circumference of the graph G is at least min｛ n,3δ *+δ,6δ ｝. The graph G was sorted into several types to be examined. The method of reduction to absurdity was used to get the above result. The properties of 3 Connected claw free of the graph were used to structure the contradiction if the longest cycle of graph G does not satisfy a given condition or does to prove the above conclusion.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
1999年第4期434-437,共4页
Journal of Northeastern University(Natural Science)
基金
国家自然科学基金
关键词
3-连通
无爪图
周长
简单图
connected,claw free graph,circumference.
