Advertisement
Published in:
2007 | OriginalPaper | Chapter
An Implicit Weighted Degree Condition for Heavy Cycles in Weighted Graphs
Authors : Bing Chen, Shenggui Zhang, T. C. Edwin Cheng
Published in: Discrete Geometry, Combinatorics and Graph Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
G
be a 2-connected weighted graph and
m
a nonnegative number. As introduced by Li as the weighted analogue of a concept due to Zhu et al, we use
id
w
(
v
) to denote the implicit weighted degree of a vertex
v
in
G
. In this paper we prove that
G
contains either a Hamilton cycle or a cycle of weight at least
m
, if the following two conditions are satisfied: (1) max {
id
w
(
u
),
id
w
(
v
)} ≥
m
/2 for each pair of nonadjacent vertices
u
and
v
that are vertices of an induced claw or an induced modified claw of
G
; (2) In each induced claw, each induced modified claw and each induced
P
4
of
G
, all the edges have the same weight. This is a common generalization of several previous results on the existence of long cycles in unweighted graphs and heavy cycles in weighted graphs.