摘要
给一个图Ｇ，定义，是Ｇ的无关集，是Ｇ中使的无关集，本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σｓ３≥ｎ。，则Ｇ包含长度至少为ｍｉｎ的圈。这个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄｍａｎ所提猜想的一个特例．
For a graph G = (V(G),E(G)) and for any v ∈ V(G) denote by N(v) the neighborhood of v in G and d(v) = |N(v) |. Let {v1, v2, v3 } be an independent set in G. We define σ3(G) = min and min In this paper, it is shown that every 1-tough graph of order n with σs3(G) > n has a cycle of length at least This result extends several known results and also solves a special case of the conjecture proposed by Broersma- Heuvel -Veldman.
出处
《数学进展》
CSCD
北大核心
1996年第1期41-50,共10页
Advances in Mathematics（China）
关键词
哈密顿圈
坚韧图
邻域并
次和
最长圈
图论
Hamiltonian cycle
circumference
1-tough graph
neighborhood union
degree sum
