高次和3连通坚韧图的周长

Estimates of the length of the longest cycles in tough graphs with high degree sums

设 G 是一个 n 阶3连通坚韧图,其周长为 c,坚韧度为τ,独立数和最小次分别为α和δ,若以σ_4表示 G 的任意四点的独立集的次和的最小值,文[1]证明了,当σ_4≥n+1/2c 时 G 的每一个最长圈为控制圈且 c≥min{n,m+1/4σ_4-α},文中改进了这个结果,证明了在同样的条件下 c≥min{n,m+1/4σ_4-α+1};进而,若σ_4≥3n-1/2,则当τ≥5/3或者α≤σ+1时,G 为哈密顿图.

Let G be a 3-connected graphs of order n with circurnference c,independence number a, minimum degree δ and toughness τ,such that d(x)+d(y)+d(z)+d(w)≥s for all tetrads of independent vertices x,y,z,w.In[1] it is shown that if τ≥1 and s≥n+c/2,then every longest cycle of G is a dominating cycle and c>min{n,n+s/4-a}.This paper has improved the results by showing that under the same conditions c≥min{n,n+s/4-a+1}.Further- more when s≥n+(n-1)/2,if τ≥5/3 or δ≥a-1,then G is Hamiltonian.