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

J. Wu, Haitze J. 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 languageUndefined
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
  • EWI-24777
  • IR-91192
  • Chord
  • 3-Connected graph
  • METIS-304108
  • Removable edge

Cite this

@article{ac6ddc9bc54e45a49587ecacd51178de,
title = "Removable edges and chords of longest cycles in 3-connected graphs",
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.",
keywords = "MSC-05C38, MSC-05C40, MSC-05C75, EWI-24777, IR-91192, Chord, 3-Connected graph, METIS-304108, Removable edge",
author = "J. Wu and Broersma, {Haitze J.} and Haiyan Kang",
note = "eemcs-eprint-24777",
year = "2014",
doi = "10.1007/s00373-013-1296-x",
language = "Undefined",
volume = "30",
pages = "743--753",
journal = "Graphs and combinatorics",
issn = "0911-0119",
publisher = "Springer",
number = "3",

}

Removable edges and chords of longest cycles in 3-connected graphs. / Wu, J.; Broersma, Haitze J.; Kang, Haiyan.

In: Graphs and combinatorics, Vol. 30, No. 3, 2014, p. 743-753.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Wu, J.

AU - Broersma, Haitze J.

AU - Kang, Haiyan

N1 - eemcs-eprint-24777

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - MSC-05C38

KW - MSC-05C40

KW - MSC-05C75

KW - EWI-24777

KW - IR-91192

KW - Chord

KW - 3-Connected graph

KW - METIS-304108

KW - Removable edge

U2 - 10.1007/s00373-013-1296-x

DO - 10.1007/s00373-013-1296-x

M3 - Article

VL - 30

SP - 743

EP - 753

JO - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 3

ER -