图的周长

The Circumferences of Graphs

设G为n阶2连通图,D(x)={y|y∈V(G)~\(x),d(x,y)≤2},δ_o=min{max{d(x),d(y)}|x,y∈V(G),d(x,y)=2},D(δ_o)={x|x∈V(G),d(x)≥δ_o},δ~*为G中的顶点度且满足:(Ⅰ)δ~*尽可能的大,(Ⅱ)对经(?)x∈D(δ_o)及D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*}有|D~*(x)|<d(x)。本文证明:G的周长至少为min{n,2max(δ~o,δ~*)}。

Let G be a n-th-order 2-connected graph and D(x) = {y|y∈V(G)\(x),d(x,y)≤2} ,δo =min{max{d(x), d(y)}|,x,y (G),d(x,y) = 2} ,0(δo} = {x|x∈V<(G),d(x)≥δo},also the degree of vertice in O and satisfies: ( I ) δ' is as great as possible,(Ⅱ) |D* (x) |<d(x) for both x∈D(δo) and D* (x) = {y|y∈(D(x)∪{x}),d(x)<δ*}. Then, the circumference of graph G is proved to be min{x,2max (δo ,δ* )} at least.