کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418933 681727 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Destroying longest cycles in graphs and digraphs
ترجمه فارسی عنوان
از بین بردن طولانی ترین چرخه ها در نمودار ها و هارفرها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 186, 11 May 2015, Pages 251–259
نویسندگان
, , , , , , ,