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