关于1坚韧图的最长圈

On the Longest Cycles of 1-Tough Graphs

令G 是 p 阶 1坚韧图,且λ=min{d(u)+d(v))|u,v∈V(G);uv∈E},δ=min{d(u)|u∈V(G)},本文证明G的周长 c(G)=p,若 P≤2λ-2δ+2;c(G)≥2λ-2δ+2,若 p>2λ-2δ+2。对某些图来说 c(G)的下界是可以达到的。

Lets G be a 1-tough graph with p vertices and λ=min{d(u)+d(v) |u, v∈V(G);uv∈E},δ=min{d(u)|u∈V(G)},it is proved that the circumference of G or c(G)=p if p<2λ-2δ+2 and c(G)≥2λ-2δ+2 if p>?2δ+2. For some of these graphs,the lower bound of c(G) is attainable.