Heavy cycles passing through some specified vertices in weighted graphs
Heavy cycles passing through some specified vertices in weighted graphs
复制标题
通过加权图中某些指定顶点的重循环
DOI：
10.1002/jgt.20066
复制
发表时间：
2005
影响因子：
0.9
通讯作者：
Shenggui Zhang
中科院分区：
文献类型：
--
作者：
J. Fujisawa;Kiyoshi Yoshimoto;Shenggui Zhang
加权图的每条边 e 都分配有一个非负数，称为 e 的权重。与顶点 υ 相关的边的权重之和称为 υ 的加权度。环的权重定义为其边的权重之和。在本文中，我们证明：（1）如果G是一个2连通加权图，使得G的最小加权度至少为d，那么对于每个给定的顶点x和y，G包含至少2d通过x和y的权循环，或者G中的每个最重循环都是哈密顿循环，并且（2）如果G是一个2连通加权图，使得每对顶点的加权度和非相邻顶点至少为 s，则对于每个顶点 y，G 包含至少经过 y 的权重循环或哈密顿循环。 AMS分类：05C45 05C38 05C35。 © 2005 Wiley periodicals, Inc. J 图论
A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory