The Chvátal-Erdös condition for cycles in triangle-free graphs
type: Item
instance of: scholarly article
title: The Chvátal-Erdös condition for cycles in triangle-free graphs
zbMATH Open document ID: 0857.05056
DOI: 10.1016/0012-365X(96)80461-4
author: Dingjun Lou
published in: Discrete Mathematics
publication date: 1996-09-04T00:00:00Z
review text: Chvátal and Erdös showed that if \(G\) is a graph whose connectivity is at least as large as its independence number, then \(G\) is Hamiltonian. Here it is established that a triangle-free graph satisfying the Chvátal-Erdös condition has cycles of every length \(n\) for \(4\leq n\leq v\), where \(v\) is the number of vertices in \(G\), unless \(G\) is \(K_{{v\over 2},{v\over 2}}\) or \(C_5\). This verifies a conjecture of D. Amar, I. Fournier and A. Germa.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 897581
zbMATH Keywords: connectivity
zbMATH Keywords: independence number
zbMATH Keywords: Hamiltonian
zbMATH Keywords: cycles
reviewed by: Linda Lesniak
MaRDI profile type: Publication
cites work: Q4892325
cites work: Pancyclism in Chvátal-Erdős' graphs
cites work: Toughness and triangle-free graphs
cites work: Q4087221
cites work: Q5422499
cites work: Q3487369
cites work: A note on Hamiltonian circuits
cites work: Q3981351
cites work: Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
cites work: Q4858147
description: scientific article; zbMATH DE number 897581