The Chvátal-Erdös condition for cycles in triangle-free graphs (Q1917498): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4892325 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pancyclism in Chvátal-Erdős' graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness and triangle-free graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4087221 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3487369 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on Hamiltonian circuits / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3981351 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4858147 / rank | |||
Normal rank |
Latest revision as of 13:12, 24 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Chvátal-Erdös condition for cycles in triangle-free graphs |
scientific article |
Statements
The Chvátal-Erdös condition for cycles in triangle-free graphs (English)
0 references
4 September 1996
0 references
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.
0 references
connectivity
0 references
independence number
0 references
Hamiltonian
0 references
cycles
0 references