کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646673 1342309 2016 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Three ways to cover a graph
ترجمه فارسی عنوان
سه راه برای پوشش یک نمودار
کلمات کلیدی
پوشش نمودار ؛ شماره فاصله؛ شماره پیگیری؛ arboricity خطی؛ arboricity کاترپیلار؛ arboricity ستاره
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

We consider the problem of covering an input graph  HH with graphs from a fixed covering class  GG. The classical covering number of HH with respect to GG is the minimum number of graphs from GG needed to cover the edges of HH without covering non-edges of HH. We introduce a unifying notion of three covering parameters with respect to GG, two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures “how far” HH is from GG in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, e.g., interval graphs and planar graphs, the local covering number has received little attention.We provide new bounds on each covering number with respect to the following covering classes: linear forests, star forests, caterpillar forests, and interval graphs. The classical graph parameters that result this way are interval number, track number, linear arboricity, star arboricity, and caterpillar arboricity. As input graphs we consider graphs of bounded degeneracy, bounded degree, bounded tree-width or bounded simple tree-width, as well as outerplanar, planar bipartite, and planar graphs. For several pairs of an input class and a covering class we determine exactly the maximum ordinary, local, and folded covering number of an input graph with respect to that covering class.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 745–758
نویسندگان
, ,