Destroying longest cycles in graphs and digraphs

Susan A. Van Aardt, Alewyn P. Burger, Jean E. Dunbar, Marietjie Frick, Bernardo Llano, Carsten Thomassen, Rita Zuazua

Research output: Contribution to journalJournal article

277 Downloads (Pure)


In 1978, C. Thomassen proved that in any graph one can destroy all the longest cycles by deleting at most one third of the vertices. We show that for graphs with circumference k≤8 it suffices to remove at most 1/k of the vertices. The Petersen graph demonstrates that this result cannot be extended to include k=9 but we show that in every graph with circumference nine we can destroy all 9-cycles by removing 1/5 of the vertices. We consider the analogous problem for digraphs and show that for digraphs with circumference k=2,3, it suffices to remove 1/k of the vertices. However this does not hold for k≥4.
Original languageEnglish
JournalDiscrete Applied Mathematics
Pages (from-to)251-259
Publication statusPublished - 2015


  • Circumference
  • Longest cycle
  • Vertex deletion
  • Directed graphs
  • Graphs and digraphs
  • Petersen graphs
  • Graph theory

Fingerprint Dive into the research topics of 'Destroying longest cycles in graphs and digraphs'. Together they form a unique fingerprint.

Cite this