Ore度和条件下赋权triangle-free图中的重圈(英文)

Heavy Cycles in Triangle-free Weighted Graphs under Ore's Degree Condition

设G是一个2-连通赋权图,且G中每一对不相邻顶点u和v都满足d^w(u)+d^w(v)≥2d.Bondy等人证明了G或者包含一个哈密尔顿圈,或者包含一个权至少为2d的圈.如果G不是哈密尔顿图,这个结论意味着G中包含一个权至少为2d的圈.但是当G是哈密尔顿图时,我们不能判断G是否包含一个权至少为2d的圈.这篇文章中,在Fujisawa的一篇文章的启发下,我们证明了当G是triangle-free图并且|V(G)|是奇数时,G中一定包含一个权至少为2d的圈,即使G是哈密尔顿图.

Let G be a 2-connected weighted graph such that dw （u） ＋ dw （v） ≥2d for every pair of nonadjacent vertices u and v in G. Bondy et al. proved that G contains either a Hamilton cycle or a cycle of weight at least 2d. If G is not hamiltonian, then this theorem implies the existence of a cycle of weight at least 2d, but in case of G is hamiltonian we cannot decide whether G has a heavy cycle or not. In this paper, motivated by a paper of Fujisawa et al., we prove that if G is triangle-free and IV（G）I is odd, then G contains a cycle of weight at least 2d even in case of G is hamiltonian.