The Chvatal-Erdos condition for cycles in triangle-free graphs

被引：12
作者：
Lou, DJ [1 ]
机构：
[1] ZHONGSHAN UNIV,DEPT COMP SCI,GUANGZHOU 510275,PEOPLES R CHINA
来源：
DISCRETE MATHEMATICS | 1996年 / 152卷 / 1-3期
关键词：
D O I：
10.1016/0012-365X(96)80461-4
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
It is proved that if G is a triangle-free graph with v vertices whose independence number does not exceed its connectivity then G has cycles of every length n for 4 less than or equal to n less than or equal to v(G) unless G = K-v/2,K-v/2 or G is a 5-cycle. This was conjectured by Amar, Fournier and Germa.
引用
收藏
页码：253 / 257
页数：5
相关论文
共 10 条
[1]  
ALDRED REL, UNPUB DIVERGENCE CON
[2]   PANCYCLISM IN CHVATAL-ERDOS GRAPHS [J].
AMAR, D ;
FOURNIER, I ;
GERMA, A .
GRAPHS AND COMBINATORICS, 1991, 7 (02) :101-112
[3]  
BAUER D, 1993, TOUGHNESS TRIANGLE F
[4]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[5]  
BONDY JA, 1973, C MATH SOC J BOLYAI, V10, P181
[6]  
CHAKROUN N, 1990, CYCLES RAYS, P75
[7]  
Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9
[8]  
FAUDREE RJ, 1991, ARS COMBINATORIA, V31, P139
[9]   CHVATAL-ERDOS CONDITIONS FOR PATHS AND CYCLES IN GRAPHS AND DIGRAPHS - A SURVEY [J].
JACKSON, B ;
ORDAZ, O .
DISCRETE MATHEMATICS, 1990, 84 (03) :241-254
[10]  
LOU D, UNPUB NEIGHBOURHOOD
1