3-连通、高次和坚韧图周长的估计(Ⅰ)

Estimates for Length of Longest Cycles in Tough Graphs with High Degree Sums (Ⅰ)

设G是一个n阶3-连通图,周长为C(G),独立数为,若G是1-坚韧的,且,则G的每一个最长圈是控制圈且;又若G是5/3-坚韧的或,则G是Hamilton图。

A number of results are established about long cycles in tough graphs with high degree sums. Let G be a 3-connected graph of order n with circumference c, independence number a and toughness r such that d(x)+d(y)+d(z)+d(w)≥s for all tetrads of independent vertices x, y, z, w. If τ≥1 and s≥ n+c/2, then every longest cycle in G is a dominating cycle and c≥min{n, n + s/4 -α}. Furthermore, when s≥n+(n -1)/2, if τ≥5/3 or δ≥a, then G is hamiltonian.