Local Clique Covering of Graphs
Local Clique Covering of Graphs
复制标题
图的局部团覆盖
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
B. Omoomi
中科院分区：
文献类型：
--
作者：
R. Javadi;Zeinab Maleki;B. Omoomi
一个简单图G的k-团覆盖是指G的一个边被它的团覆盖，使得每个顶点至多包含在k个团中。G允许一个k-团覆盖的最小k称为G的局部团覆盖数，记为lcc（G）。局部团覆盖数可以看作是团覆盖数的局部对应，其等于覆盖所有边的团的最小总数。本文研究了该问题的几个方面，并讨论了它与其他已知问题的关系。此外，我们还研究了无爪图及其子类的局部团覆盖数。特别地，证明了每一个无爪图的局部团覆盖数至多为$cDelta / logDelta$，其中$Delta$是图的最大度，$c$是一个泛常数。它还表明，该界是紧的，直到一个常数因子。进一步证明了线性区间图的局部团数的界为$logDelta + 1/2loglogDelta + O（1）$。最后，作为副产品，得到了一个新的集合系统相交对的Bollobas型不等式。
A k-clique covering of a simple graph G, is an edge covering of G by its cliques such that each vertex is contained in at most k cliques. The smallest k for which G admits a k-clique covering is called local clique cover number of G and is denoted by $lcc(G)$. Local clique cover number can be viewed as the local counterpart of the clique cover number which is equal to the minimum total number of cliques covering all edges. In this paper, several aspects of the problem are studied and its relationships to other well-known problems are discussed. Moreover, the local clique cover number of claw-free graphs and its subclasses are notably investigated. In particular, it is proved that local clique cover number of every claw-free graph is at most $cDelta / logDelta$, where $Delta$ is the maximum degree of the graph and $c$ is a universal constant. It is also shown that the bound is tight, up to a constant factor. Furthermore, it is established that local clique number of the linear interval graphs is bounded by $logDelta + 1/2 log logDelta + O(1)$. Finally, as a by-product, a new Bollobas-type inequality is obtained for the intersecting pairs of set systems.