PDF

Discussiones Mathematicae Graph Theory 22(1) (2002) 7-15
DOI: https://doi.org/10.7151/dmgt.1154

HEAVY CYCLES IN WEIGHTED GRAPHS

J. Adrian Bondy Laboratoire de Mathématiques Discrètes Université Claude Bernard Lyon 1, 69622 Villeurbanne Cedex, France

Hajo J. Broersma Faculty of Applied Mathematics University of Twente P.O. Box 217, 7500 AE Enschede, The Netherlands

Jan van den Heuvel Department of Mathematics and Statistics Simon Fraser University Burnaby, B.C., Canada V5A 1S6

Henk Jan Veldman Faculty of Applied Mathematics University of Twente P.O. Box 217, 7500 AE Enschede, The Netherlands

The first three authors would like to dedicate this paper to Henk Jan Veldman, a valued colleague and beloved friend who died October 12, 1998.

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.

Keywords: weighted graph, (long, optimal, Hamilton) cycle, (edge-, vertex-)weighting, weighted degree.

2000 Mathematics Subject Classifications: 05C45, 05C38, 05C35.

References

[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.
[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.
[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.
[4]	J.A. Bondy and G. Fan, Cycles in weighted graphs, Combinatorica 11 (1991) 191-205, doi: 10.1007/BF01205072.
[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.
[6]	J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London and Elsevier, New York, 1976).
[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.
[8]	L. Pósa, On the circuits of finite graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 355-361.
[9]	T. Spencer (Personal communication, 1992).
[10]	Yan Lirong (Personal communication, 1990).

Received 27 June 2000
Revised 22 May 2001