Three ways to cover a graph
Three ways to cover a graph
复制标题
覆盖图表的三种方法
DOI：
10.1016/j.disc.2015.10.023
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Torsten Ueckerdt
中科院分区：
文献类型：
--
作者：
Kolja B. Knauer;Torsten Ueckerdt
考虑了用固定覆盖类G中的图覆盖输入图H的问题。H关于G的经典覆盖数是指G中覆盖H的边而不覆盖H的非边所需的最小图数。我们引入了一个统一的概念，三个覆盖参数G，其中两个是新的概念，只考虑在特殊情况下之前：本地和折叠覆盖数。每一个参数都以不同的方式测量H离G有多远。然而，折叠覆盖数已经深入研究了一些覆盖类，如区间图和平面图，局部覆盖数很少受到关注。我们提供了新的边界上的每个覆盖数关于以下覆盖类：线性森林，星星森林，毛毛虫森林，和区间图。由此得到的经典图参数有区间数、迹数、线性荫度、星星荫度和毛虫荫度。作为输入图，我们考虑有界退化，有界度，有界树宽度或有界简单树宽度的图，以及外平面，平面二分图和平面图。对于几对输入类和覆盖类，我们确定的最大普通，本地和折叠覆盖数的输入图关于该覆盖类。
We consider the problem of covering an input graph H with graphs from a fixed covering class G. The classical covering number of H with respect to G is the minimum number of graphs from G needed to cover the edges of H without covering non-edges of H. We introduce a unifying notion of three covering parameters with respect to G, two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures “how far” H is from G in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, eg, 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.
登录
查看更多内容
每个外平面图都是两个区间图的并集
DOI：
--
发表时间：
1999
期刊：
影响因子：
--
作者：
A. Kostochka;D. West
通讯作者：
D. West
影响因子：
1.1
作者：
Minghui Jiang
通讯作者：
Minghui Jiang
DOI：
--
发表时间：
2007
期刊：
Graphs Comb.
影响因子：
--
作者：
Jinquan Dong;Yanpei Liu
通讯作者：
Yanpei Liu
Biclique 盖板和隔板
影响因子：
0.7
作者：
Trevor Pinto
通讯作者：
Trevor Pinto
关于平面图和外平面图的弯曲数
DOI：
--
发表时间：
2011
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
Daniel Heldt;K. Knauer;T. Ueckerdt
通讯作者：
T. Ueckerdt