Geodesic
Heavy cycles in weighted graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 7-15

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: weighted graph, (long, optimal, Hamilton) cycle, (edge-, vertex-)weighting, weighted degree 
@article{DMGT_2002_22_1_a1,
     author = {Bondy, J. and Broersma, Hajo and van den Heuvel, Jan and Veldman, Henk},
     title = {Heavy cycles in weighted graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {7--15},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a1/}
}
TY  - JOUR
AU  - Bondy, J.
AU  - Broersma, Hajo
AU  - van den Heuvel, Jan
AU  - Veldman, Henk
TI  - Heavy cycles in weighted graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 7
EP  - 15
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a1/
LA  - en
ID  - DMGT_2002_22_1_a1
ER  - 
%0 Journal Article
%A Bondy, J.
%A Broersma, Hajo
%A van den Heuvel, Jan
%A Veldman, Henk
%T Heavy cycles in weighted graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 7-15
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a1/
%G en
%F DMGT_2002_22_1_a1
Bondy, J.; Broersma, Hajo; van den Heuvel, Jan; Veldman, Henk. Heavy cycles in weighted graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 1, pp. 7-15. http://geodesic.mathdoc.fr/item/DMGT_2002_22_1_a1/