Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418933 | Discrete Applied Mathematics | 2015 | 9 Pages |
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≤8k≤8 it suffices to remove at most 1/k1/k of the vertices. The Petersen graph demonstrates that this result cannot be extended to include k=9k=9 but we show that in every graph with circumference nine we can destroy all 9-cycles by removing 1/51/5 of the vertices. We consider the analogous problem for digraphs and show that for digraphs with circumference k=2,3k=2,3, it suffices to remove 1/k1/k of the vertices. However this does not hold for k≥4k≥4.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Susan A. van Aardt, Alewyn P. Burger, Jean E. Dunbar, Marietjie Frick, Bernardo Llano, Carsten Thomassen, Rita Zuazua,