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

Abstract

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

How to cite

top

Shenggui 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. [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. [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. [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. [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan London and Elsevier, New York, 1976). 
  5. [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. [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. [7] L. Pósa, On the circuits of finite graphs, Magyar Tud. Math. Kutató Int. Közl. 8 (1963) 355-361. Zbl0133.16702
  8. [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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.