# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

# Discussiones Mathematicae Graph Theory

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