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 articleResearchpeer-review

358 Downloads (Pure)

Abstract

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
Volume186
Pages (from-to)251-259
ISSN0166-218X
DOIs
Publication statusPublished - 2015

Keywords

  • 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