# A σ₃ type condition for heavy cycles in weighted graphs

Shenggui Zhang; Xueliang Li; Hajo Broersma

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 159-166
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topShenggui Zhang, Xueliang Li, and Hajo Broersma. "A σ₃ type condition for heavy cycles in weighted graphs." Discussiones Mathematicae Graph Theory 21.2 (2001): 159-166. <http://eudml.org/doc/270379>.

@article{ShengguiZhang2001,

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 $d^w(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.},

author = {Shenggui Zhang, Xueliang Li, Hajo Broersma},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {weighted graph; (long, heavy, Hamilton) cycle; weighted degree; (weighted) degree sum; degree sum; Hamilton cycle},

language = {eng},

number = {2},

pages = {159-166},

title = {A σ₃ type condition for heavy cycles in weighted graphs},

url = {http://eudml.org/doc/270379},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Shenggui Zhang

AU - Xueliang Li

AU - Hajo Broersma

TI - A σ₃ type condition for heavy cycles in weighted graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 159

EP - 166

AB - 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 $d^w(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.

LA - eng

KW - weighted graph; (long, heavy, Hamilton) cycle; weighted degree; (weighted) degree sum; degree sum; Hamilton cycle

UR - http://eudml.org/doc/270379

ER -

## References

top- [1] J.A. Bondy, Large cycles in graphs, Discrete Math. 1 (1971) 121-132, doi: 10.1016/0012-365X(71)90019-7. Zbl0224.05120
- [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. Zbl1012.05104
- [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. Zbl0673.05056
- [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. Zbl0047.17001
- [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. Zbl0576.05035
- [7] L. Pósa, On the circuits of finite graphs, Magyar Tud. Math. Kutató Int. Közl. 8 (1963) 355-361. Zbl0133.16702
- [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. Zbl0994.05090

## Citations in EuDML Documents

top## NotesEmbed ?

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