3-连通无爪图的周长  

Circumference in 3 Connected Claw Free Graphs

作　　者：车向凯[1] 

机构地区：[1]东北大学理学院

出　　处：《东北大学学报（自然科学版）》1999年第3期333-336,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金

摘　　要：设Ｇ为ｎ阶３连通无爪图·δ＝ｍｉｎ｛ｄ（ｘ）｜ｘ∈Ｖ（Ｇ）｝，δ＝ｍｉｎ｛ｍａｘ（ｄ（ｘ），ｄ（ｙ））｜ｘ，ｙ∈Ｖ（Ｇ），ｄ（ｘ，ｙ）＝２｝，则Ｃ（Ｇ）≥ｍｉｎ｛ｎ，３δ＋δ，６δ｝·采用反证法，将图Ｇ分为若干情形·在每一种情形中，利用图Ｇ的３连通性和无爪性，构造若图Ｇ的最长圈不满足已给条件的矛盾·It is proved that if G is a 3 connected claw free graph on n vertices with the minimum degree δ and δ *=min{max( d(x),d(y))|x,y∈V(G),d(x,y)=2} ,then the circumference of the graph G is at least min{ n,3δ *+δ,6δ} .The graph G was sorted into several types and the method of reduction to absurdity was used to get the result. The properties of 3 connected claw free were used to structure the contradiction if the longest cycle of graph G does not satisfy a given condition in each type to prove the above conclusion.

关 键 词：无爪图 周长 连通图 3-连通图 

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