Abstract
We verify two special cases of Thomassen’s conjecture of 1976 stating that every longest cycle in a 3-connected graph contains a chord. We prove that Thomassen’s conjecture is true for two classes of 3-connected graphs that have a bounded number of removable edges on or off a longest cycle. Here an edge e of a 3-connected graph G is said to be removable if G-e is still 3-connected or a subdivision of a 3-connected (multi)graph. We give examples to show that these classes are not covered by previous results.
| Original language | English |
|---|---|
| Pages (from-to) | 743-753 |
| Number of pages | 11 |
| Journal | Graphs and combinatorics |
| Volume | 30 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 2014 |
Keywords
- MSC-05C38
- MSC-05C40
- MSC-05C75
- Chord
- 3-Connected graph
- Removable edge
- 2023 OA procedure
Fingerprint
Dive into the research topics of 'Removable edges and chords of longest cycles in 3-connected graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver