کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949942 1440207 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A lower bound on the order of the largest induced forest in planar graphs with high girth
ترجمه فارسی عنوان
محدوده پایین تر از ترتیب بزرگترین جنگل القا شده در نمودارهای مسطح با طول زیاد است
کلمات کلیدی
جنگل منجر شده، بازخورد مجموعه رشته، گردن بزرگ، نمودار پلانار،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We give here new lower bounds on the size of a largest induced forest in planar graphs with high girth. This is equivalent to upper bounds on the size of a smallest feedback vertex set. In particular, we prove that a planar graph with girth g and size m has a feedback vertex set of size at most 4m3g, improving the trivial bound of 2mg. We also prove that every 2-connected graph with maximum degree 3 and order n has a feedback vertex set of size at most n+23.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 99-107
نویسندگان
, , ,