An implicit degree condition for long cycles in 2-connected graphs

被引：17

作者：

Chen, Bing ^{[1
]}

Zhang, Shenggui ^{[1
]}

机构：

[1] Northwestern Polytech Univ, Dept Appl Math, Xian 710072, Shaanxi, Peoples R China

来源：

APPLIED MATHEMATICS LETTERS | 2006年 / 19卷 / 11期

基金：

中国国家自然科学基金;

关键词：

long cycle; implicit degree; induced claw (modified claw);

D O I：

10.1016/j.aml.2005.12.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let id(v) denote the implicit degree of a vertex v. In this work we prove that: If G is a 2-connected graph with max{id(u), id(nu)} : c/2 for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G, then G contains either a Hamilton cycle or a cycle of length at least c. This extends several previous results on the existence of long cycles in graphs. (c) 2006 Elsevier Ltd. All rights reserved.

引用

页码：1148 / 1151

页数：4

共 8 条

[1] A GENERALIZATION OF FAN CONDITION FOR HAMILTONICITY, PANCYCLICITY, AND HAMILTONIAN CONNECTEDNESS
BEDROSSIAN, P
CHEN, G
SCHELP, RH
[J]. DISCRETE MATHEMATICS, 1993, 115 (1-3) : 39 - 50
[2] Bermond Jean-Claude., 1976, 5th British Combinatorial Conference, 1975, Congressus Numerantium 15, Utilitas Math Pub, P41
[3] Bondy J.A., 1971, Discrete Math., V1, P121, DOI DOI 10.1016/0012-365X(71)90019-7
[4] Chen G., 1986, J CENTRAL CHINA NORM, V3, P39
[5] NEW SUFFICIENT CONDITIONS FOR CYCLES IN GRAPHS
FAN, GH
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 37 (03) : 221 - 227
[6] LOWER BOUND FOR CIRCUMFERENCE OF A GRAPH
LINIAL, N
[J]. DISCRETE MATHEMATICS, 1976, 15 (03) : 297 - 300
[7] POSA L, 1963, CIRCUITS FINITE GRAP, V8, P355
[8] ZHU Y, 1989, GRAPHS COMBIN, P283

← 1 →