Premium
Heavy cycles passing through some specified vertices in weighted graphs
Author(s) -
Fujisawa Jun,
Yoshimoto Kiyoshi,
Zhang Shenggui
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20066
Subject(s) - combinatorics , mathematics , hamiltonian path , wheel graph , vertex (graph theory) , graph , discrete mathematics , graph power , line graph
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 2 d 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