DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 21(2) (2001) 159-166
DOI: 10.7151/dmgt.1140

A σ3 TYPE CONDITION FOR HEAVY CYCLES IN WEIGHTED GRAPHS

Shenggui Zhang and  Xueliang Li

Department of Applied Mathematics
Northwestern Polytechnical University
Xi'an, Shaanxi 710072, P.R. China

Hajo Broersma

Faculty of Mathematical Sciences
University of Twente
P.O. Box 217
7500 AE Enschede, The Netherlands

Abstract

A weighted graph is a graph in which each edge e is assigned a non-negative number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges. The weighted degree dw(v) of a vertex v is the sum of the weights of the edges incident with v. In this paper, we prove the following result: Suppose G is a 2-connected weighted graph which satisfies the following conditions: 1. The weighted degree sum of any three independent vertices is at least m; 2. w(xz) = w(yz) for every vertex z ∈ N(x)∩N(y) with d(x,y) = 2; 3. In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains either a Hamilton cycle or a cycle of weight at least 2m/3. This generalizes a theorem of Fournier and Fraisse on the existence of long cycles in k-connected unweighted graphs in the case k = 2. Our proof of the above result also suggests a new proof to the theorem of Fournier and Fraisse in the case k = 2.

Keywords: weighted graph, (long, heavy, Hamilton) cycle, weighted degree, (weighted) degree sum.

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

References

[1] J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (1971) 121-132, doi: 10.1016/0012-365X(71)90019-7.
[2] J.A. Bondy, H.J. Broersma, J. van den Heuvel and H.J. Veldman, Heavy cycles in weighted graphs, to appear in Discuss. Math. Graph Theory, doi: 10.7151/dmgt.1154.
[3] J.A. Bondy and G. Fan, Optimal paths and cycles in weighted graphs, Ann. Discrete Math. 41 (1989) 53-69, doi: 10.1016/S0167-5060(08)70449-7.
[4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan London and Elsevier, New York, 1976).
[5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (3) (1952) 69-81, doi: 10.1112/plms/s3-2.1.69.
[6] I. Fournier and P. Fraisse, On a conjecture of Bondy, J. Combin. Theory (B) 39 (1985) 17-26, doi: 10.1016/0095-8956(85)90035-8.
[7] L. Pósa, On the circuits of finite graphs, Magyar Tud. Math. Kutató Int. Közl. 8 (1963) 355-361.
[8] S. Zhang, X. Li and H.J. Broersma, A Fan type condition for heavy cycles in weighted graphs, to appear in Graphs and Combinatorics.

Received 7 February 2000