Bounding the vertex cover number of a hypergraph
Bounding the vertex cover number of a hypergraph
复制标题
限制超图的顶点覆盖数
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
P. Winkler
中科院分区：
文献类型：
--
作者：
G. Ding;P. Seymour;P. Winkler
摘要对于一个超图H，我们用(i)τ(H)表示使k个顶点集合满足所有边的最小值，(ii)ν(H)表示使某些边成对不相交的最大值，(iii)λ(H)表示使H的关联矩阵有完整图k的关联矩阵的转置作为子矩阵的最大值≥2。
AbstractFor a hypergraphH, we denote by(i)τ(H) the minimumk such that some set ofk vertices meets all the edges,(ii)ν(H) the maximumk such that somek edges are pairwise disjoint, and(iii)λ(H) the maximumk≥2 such that the incidence matrix ofH has as a submatrix the transpose of the incidence matrix of the complete graphKk.
We show that τ(H) is bounded above by a function of ν(H) and λ(H), and indeed that if λ(H) is bounded by a constant then τ(H) is at most a polynomial function of ν(H).