Abstract | ||
---|---|---|
A weighted graph is one in which every edge e is assigneda nonnegative number, called the weight of e. The sum of theweights of the edges incident with a vertex υ is called theweighted degree of υ. The weight of a cycle is defined asthe sum of the weights of its edges. In this paper, we prove that:(1) if G is a 2-connected weighted graph such that theminimum weighted degree of G is at least d, then forevery given vertices x and y, either Gcontains a cycle of weight at least 2d passing through bothof x and y or every heaviest cycle in G is ahamiltonian cycle, and (2) if G is a 2-connected weightedgraph such that the weighted degree sum of every pair ofnonadjacent vertices is at least s, then for every vertexy, G contains either a cycle of weight at leasts passing through y or a hamiltonian cycle. AMSclassification: 05C45 05C38 05C35. © 2005 Wiley Periodicals,Inc. J Graph Theory |
Year | DOI | Venue |
---|---|---|
2005 | 10.1002/jgt.v49:2 | Journal of Graph Theory |
Keywords | Field | DocType |
hamiltonian cycle | Discrete mathematics,Topology,Wheel graph,Combinatorics,Graph toughness,Loop (graph theory),Graph power,Cycle graph,Neighbourhood (graph theory),Regular graph,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
49 | 2 | 0364-9024 |
Citations | PageRank | References |
3 | 0.56 | 6 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jun Fujisawa | 1 | 29 | 10.54 |
Kiyoshi Yoshimoto | 2 | 133 | 22.65 |
Shenggui Zhang | 3 | 263 | 47.21 |