Given a hypergraph H(V,E),a set of vertices S⊆V is a vertex cover if every edge has at least one vertex in S.The vertex cover number is the minimum cardinality of a vertex cover,denoted byτ(H).In this paper,we prove ...Given a hypergraph H(V,E),a set of vertices S⊆V is a vertex cover if every edge has at least one vertex in S.The vertex cover number is the minimum cardinality of a vertex cover,denoted byτ(H).In this paper,we prove that for every 3-uniform connected hypergraph H(V,E),τ(H)≤2m3+1/3 holds on where m is the number of edges.Furthermore,the equality holds on if and only if H(V,E)is a hypertree with perfect matching.展开更多
基金This paper was supported by the National Natural Science Foundation of China (No. 11901605).
文摘Given a hypergraph H(V,E),a set of vertices S⊆V is a vertex cover if every edge has at least one vertex in S.The vertex cover number is the minimum cardinality of a vertex cover,denoted byτ(H).In this paper,we prove that for every 3-uniform connected hypergraph H(V,E),τ(H)≤2m3+1/3 holds on where m is the number of edges.Furthermore,the equality holds on if and only if H(V,E)is a hypertree with perfect matching.
