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

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

作　　者：贺东奇[1] 

机构地区：[1]北京医科大学生物数学与生物统计教研室,北京100083

出　　处：《数学的实践与认识》1999年第4期85-92,共8页Mathematics in Practice and Theory

摘　　要：设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.

关 键 词：坚韧图 点独立数 周长 3-连通图 估计 哈密顿圈 

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