Geodesic
A σ₃ type condition for heavy cycles in weighted graphs
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 159-166

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: weighted graph, (long, heavy, Hamilton) cycle, weighted degree, (weighted) degree sum 
@article{DMGT_2001_21_2_a1,
     author = {Zhang, Shenggui and Li, Xueliang and Broersma, Hajo},
     title = {A \ensuremath{\sigma}₃ type condition for heavy cycles in weighted graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {159--166},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a1/}
}
TY  - JOUR
AU  - Zhang, Shenggui
AU  - Li, Xueliang
AU  - Broersma, Hajo
TI  - A σ₃ type condition for heavy cycles in weighted graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 159
EP  - 166
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a1/
LA  - en
ID  - DMGT_2001_21_2_a1
ER  - 
%0 Journal Article
%A Zhang, Shenggui
%A Li, Xueliang
%A Broersma, Hajo
%T A σ₃ type condition for heavy cycles in weighted graphs
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 159-166
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a1/
%G en
%F DMGT_2001_21_2_a1
Zhang, Shenggui; Li, Xueliang; Broersma, Hajo. A σ₃ type condition for heavy cycles in weighted graphs. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 159-166. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a1/