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

Abstract

top
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.

How to cite

top

J. 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. [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. [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. [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. [4] J.A. Bondy and G. Fan, Cycles in weighted graphs, Combinatorica 11 (1991) 191-205, doi: 10.1007/BF01205072. Zbl0763.05051
  5. [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. [6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976). Zbl1226.05083
  7. [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. [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. [9] T. Spencer (Personal communication, 1992). 
  10. [10] Yan Lirong (Personal communication, 1990). 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.