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 hypergraphH(V, E), τ(H) ≤ 2m/3+1 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.
Zhuo Diao
. On the Vertex Cover Number of 3-Uniform Hypergraph[J]. Journal of the Operations Research Society of China, 2021
, 9(2)
: 427
-440
.
DOI: 10.1007/s40305-019-00284-7
[1] Berge, C.: Hypergraphs: Combinatorics of Finite Sets. Elsevier, New York (1989)
[2] Okun, M.: On approximation of the vertex cover problem in hypergraphs. Discrete Optim. 2(1), 101–111(2005)
[3] Seymour, P., Ding, G., Winkler, P.: Bounding the vertex cover number of a hypergraph. Combinatorica 14(1), 23–34(1994)
[4] Kalariya, K.N., Thakkar, D.K.: Vertex covering and stability in hypergraphs. Int. J. Comput. Appl. Math. 11(1), 61–69(2016)
[5] Asratian, A.S., Kuzjurin, N.N.: On the number of nearly perfect matchings in almost regular uniform hypergraphs. Discrete Math. 207(1–3), 1–8(1999)
[6] Kim, J.H., Alon, N., Spencer, J.: Nearly perfect matchings in regular simple hypergraphs. Isr. J. Math. 100(1), 171–187(1997)
