کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903659 | 1632756 | 2017 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum size of feedback vertex sets of planar graphs of girth at least five
ترجمه فارسی عنوان
حداقل اندازه مجموعه بازه های بازتوزیع گرافهای مسطح حداقل عرض پنج
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A feedback vertex set of a graph is a subset of vertices intersecting all cycles. We provide tight upper bounds on the size of a minimum feedback vertex set in planar graphs of girth at least five. We prove that if G is a connected planar graph of girth at least five on n vertices and m edges, then G has a feedback vertex set of size at most 2mân+27. By Euler's formula, this implies that G has a feedback vertex set of size at most m5 and nâ23. These results not only improve a result of Dross, Montassier and Pinlou and confirm the girth-5 case of one of their conjectures, but also make the best known progress towards a conjecture of Kowalik, Lužar and Å krekovski and solve the subcubic case of their conjecture. An important step of our proof is providing an upper bound on the size of minimum feedback vertex sets of subcubic graphs with girth at least five with no induced subdivision of members of a finite family of non-planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 61, March 2017, Pages 138-150
Journal: European Journal of Combinatorics - Volume 61, March 2017, Pages 138-150
نویسندگان
Tom Kelly, Chun-Hung Liu,