Ore-type degree condition for heavy paths in weighted graphs
Ore-type degree condition for heavy paths in weighted graphs
复制标题
DOI：
10.1016/j.disc.2005.06.006
复制
发表时间：
2005-09
期刊：
影响因子：
--
通讯作者：
H. Enomoto;J. Fujisawa;K. Ota
中科院分区：
文献类型：
--
作者：
H. Enomoto;J. Fujisawa;K. Ota
一个赋权图是指每个边e都被赋予一个非负数w（e），称为e的权。对于赋权图的顶点v，dw（v）是与v相关联的边的权之和，而路的权是属于它的边的权之和.本文给出了赋权图有连接两个指定顶点的重路的一个充分条件.设G是一个2-连通赋权图，x和y是G的不同顶点.设对每对不相邻的顶点u和v∈V（G）<${x，y}，有dw（u）+dw（v）<$2d.则x和y由一条权至少为d的路连接，或由一条汉密尔顿路连接.此外，我们考虑了G中有一些顶点的权度不被假定的情况.
A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, dw(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the weights of the edges belonging to it. In this paper, we give a sufficient condition for a weighted graph to have a heavy path which joins two specified vertices. Let G be a 2-connected weighted graph and let x and y be distinct vertices of G. Suppose that dw(u)+dw(v)⩾2d for every pair of non-adjacent vertices u and v∈V(G)⧹{x,y}. Then x and y are joined by a path of weight at least d, or they are joined by a Hamilton path. Also, we consider the case when G has some vertices whose weighted degree are not assumed.