کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646938 1342320 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Feedback vertex sets in cubic multigraphs
ترجمه فارسی عنوان
مجموعه رأی های بازخورد در چند تصویر چند بعدی
کلمات کلیدی
بازخورد مجموعه رشته، جنگل منجر شده است
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A set of vertices of a multigraph whose removal produces a forest is a feedback vertex set. For a connected cubic multigraph GG of order nn at least 9, we show the existence of a feedback vertex set of order at most 13(n+2ℓ+me+k4+), where ℓℓ is the number of loops of GG, meme is the number of multiple edges of GG, and k4+ is the number of submultigraphs of GG that arise from K4K4 by subdividing one edge. This bound is best possible and implies several known bounds.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 12, 6 December 2015, Pages 2179–2185
نویسندگان
, ,