TY - JOUR
T1 - Heavy cycles passing through some specified vertices in weighted graphs
AU - Fujisawa, Jun
AU - Yoshimoto, Kiyoshi
AU - Zhang, Shenggui
PY - 2005/6
Y1 - 2005/6
N2 - 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 v is called the weighted degree of v. 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.
AB - 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 v is called the weighted degree of v. 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.
KW - (Heavy, hamiltonian) cycle
KW - (Weighted) degree sum
KW - Minimum (weighted) degree
KW - Weighted graph
UR - http://www.scopus.com/inward/record.url?scp=20544453646&partnerID=8YFLogxK
U2 - 10.1002/jgt.20066
DO - 10.1002/jgt.20066
M3 - 文章
AN - SCOPUS:20544453646
SN - 0364-9024
VL - 49
SP - 93
EP - 103
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 2
ER -