Removable edges and chords of longest cycles in 3-connected graphs

Jichang Wu, Hajo Broersma, Haiyan Kang

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)

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 languageEnglish
Pages (from-to)743-753
Number of pages11
JournalGraphs and combinatorics
Volume30
Issue number3
DOIs
Publication statusPublished - 2014

Keywords

  • MSC-05C38
  • MSC-05C40
  • MSC-05C75
  • Chord
  • 3-Connected graph
  • Removable edge

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