您当前所在位置: 首页 > 学者

李学良

  • 50浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 57下载

  • 0评论

  • 引用

期刊论文

Heavy paths and cycles in weighted graphs☆

李学良Shenggui Zhang a* Xueliang Li a Hajo Broersma b

Discrete Mathematics 223 (2000) 327-336,-0001,():

URL:

摘要/描述

A weighted graph is a graph in which each edge is assigned a non-negative number, called the weight. The weight of a path (cycle) is the sum of the weights of its edges. The weighted degree of a vertex is the sum of the weights of the edges incident with the vertex. A usual (unweighted) graph can be considered as a weighted graph with constant weight 1. In this paper, it is proved that for a 2-connected weighted graph, if every vertex has weighted degree at least d, then for any given vertex y, either y is contained in a cycle with weight at least 2d or every heaviest cycle is a Hamilton cycle. This result is a common generalization of Gr?tschel's theorem and Bondy-Fan's theorem assuring the existence of a cycle with weight at least 2d on the same condition. Also, as a tool for proving this result, we show a result concerning heavy paths joining two specific vertices and passing through one given vertex.

【免责声明】以下全部内容由[李学良]上传于[2006年02月14日 23时13分00秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。

我要评论

全部评论 0

本学者其他成果

    同领域成果