Not every 2-tough graph is Hamiltonian (Q1962051): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(4 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Hajo J. Broersma / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Henk Jan Veldman / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q29037944 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness, minimum degree, and the existence of 2‐factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Chordality and 2-factors in tough graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness, minimum degree, and the existence of 2‐factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3866156 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3097395 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4378526 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tough graphs and Hamiltonian circuits. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Toughness and the existence ofk-factors / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0166-218x(99)00141-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2007167081 / rank | |||
Normal rank |
Latest revision as of 11:32, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Not every 2-tough graph is Hamiltonian |
scientific article |
Statements
Not every 2-tough graph is Hamiltonian (English)
0 references
9 April 2000
0 references
A long standing conjecture due to V. Chvátal was that any \(2\)-tough graph is Hamiltonian. A very clever example is presented that disproves this conjecture. More specifically, it is shown for any \(\epsilon > 0\), there is a \((9/4 - \epsilon)\)-tough graph that does not contain a Hamiltonian path. In lack manner a \((7/4 - \epsilon)\)-tough chordal graph that has no Hamiltonian path is presented. The latter result gives a lower bound to the toughness that will imply Hamiltonian in chordal graphs as opposed to the upper bound of \(18\) of \textit{G. Chen, M. S. Jacobson, A. Kézdy} and \textit{J. E. Lehel} [Networks 31, No. 1, 29-38 (1998; Zbl 0894.90150)].
0 references
Hamiltonian
0 references
tough
0 references
\(2\)-tough
0 references
chordal
0 references
traceable
0 references