# Heavy cycles in weighted graphs

J. Adrian Bondy; Hajo J. Broersma; Jan van den Heuvel; Henk Jan Veldman

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 1, page 7-15
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJ. Adrian Bondy, et al. "Heavy cycles in weighted graphs." Discussiones Mathematicae Graph Theory 22.1 (2002): 7-15. <http://eudml.org/doc/270548>.

@article{J2002,

abstract = {An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such that w(v) ≥ r for every vertex v of G. Then either G contains a cycle of weight at least 2r or every optimal cycle of G is a Hamilton cycle. We prove the following weighted analogue of a generalization of Dirac's result that was first proved by Pósa. Let G be a 2-connected weighted graph such that w(u)+w(v) ≥ s for every pair of nonadjacent vertices u and v. Then G contains either a cycle of weight at least s or a Hamilton cycle. Examples show that the second conclusion cannot be replaced by the stronger second conclusion from the result of Bondy and Fan. However, we characterize a natural class of edge-weightings for which these two conclusions are equivalent, and show that such edge-weightings can be recognized in time linear in the number of edges.},

author = {J. Adrian Bondy, Hajo J. Broersma, Jan van den Heuvel, Henk Jan Veldman},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {weighted graph; (long, optimal, Hamilton) cycle; (edge-, vertex-)weighting; weighted degree},

language = {eng},

number = {1},

pages = {7-15},

title = {Heavy cycles in weighted graphs},

url = {http://eudml.org/doc/270548},

volume = {22},

year = {2002},

}

TY - JOUR

AU - J. Adrian Bondy

AU - Hajo J. Broersma

AU - Jan van den Heuvel

AU - Henk Jan Veldman

TI - Heavy cycles in weighted graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 1

SP - 7

EP - 15

AB - An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such that w(v) ≥ r for every vertex v of G. Then either G contains a cycle of weight at least 2r or every optimal cycle of G is a Hamilton cycle. We prove the following weighted analogue of a generalization of Dirac's result that was first proved by Pósa. Let G be a 2-connected weighted graph such that w(u)+w(v) ≥ s for every pair of nonadjacent vertices u and v. Then G contains either a cycle of weight at least s or a Hamilton cycle. Examples show that the second conclusion cannot be replaced by the stronger second conclusion from the result of Bondy and Fan. However, we characterize a natural class of edge-weightings for which these two conclusions are equivalent, and show that such edge-weightings can be recognized in time linear in the number of edges.

LA - eng

KW - weighted graph; (long, optimal, Hamilton) cycle; (edge-, vertex-)weighting; weighted degree

UR - http://eudml.org/doc/270548

ER -

## References

top- [1] B. Bollobás and A.D. Scott, A proof of a conjecture of Bondy concerning paths in weighted digraphs, J. Combin. Theory (B) 66 (1996) 283-292, doi: 10.1006/jctb.1996.0021. Zbl0881.05072
- [2] J.A. Bondy, Basic graph theory: paths and circuits, in: R.L. Graham, M. Grötschel and L. Lovász, eds., Handbook of Combinatorics (North-Holland, Amsterdam, 1995) 3-110. Zbl0849.05044
- [3] J.A. Bondy and G. Fan, Optimal paths and cycles in weighted graphs, Annals of Discrete Math. 41 (1989) 53-69, doi: 10.1016/S0167-5060(08)70449-7. Zbl0673.05056
- [4] J.A. Bondy and G. Fan, Cycles in weighted graphs, Combinatorica 11 (1991) 191-205, doi: 10.1007/BF01205072. Zbl0763.05051
- [5] J.A. Bondy and S.C. Locke, Relative lengths of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122, doi: 10.1016/0012-365X(81)90159-X. Zbl0448.05044
- [6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
- [7] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
- [8] L. Pósa, On the circuits of finite graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 355-361. Zbl0133.16702
- [9] T. Spencer (Personal communication, 1992).
- [10] Yan Lirong (Personal communication, 1990).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.