Let H be a hypergraph with vertex set V(H) and hyperedge set E(H). We call a vertex set R $\subseteq$ V(H) a transversal if it has a nonempty intersection with every hyperedge of H. The transversal number, denoted by τ(H), is the minimum cardinality of transversals. In 2021, Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most $\frac{2 m+1}{3}$, that is, τ(H) $\frac{2 m+1}{3}$, where m is the size of H. Moreover, they gave the necessary and sufficient conditions to reach the upper bound, namely τ(H) = $\frac{2 m+1}{3}$, if and only if H is a hypertree with a perfect matching. In this paper, we investigate the transversal number of connected kuniform hypergraphs for k ≥ 3. We confirm that τ(H) $\frac{(k-1) m+1}{k}$ for any k-uniform hypergraph H with size m. Furthermore, we show that τ(H) = $\frac{(k-1) m+1}{k}$ if and only if H is a hypertree with a perfect matching, which generalizes the results of Diao.
Zi-An Chen, Bin Chen
. An Upper Bound for the Transversal Number of Connected k-Uniform Hypergraphs[J]. Journal of the Operations Research Society of China, 2024
, 12(3)
: 829
-835
.
DOI: 10.1007/s40305-022-00445-1
[1] Tuza, Z.: Covering all cliques of a graph. Discrete Math. 86, 117-126(1990)
[2] Alon, N.: Transversal numbers of uniform hypergraphs. Graphs Combin. 6, 1-4(1990)
[3] Lai, F.C., Chang, G.J.: An upper bound for the transversal numbers of 4-uniform hypergraphs. J. Combin. Theory Ser. B. 50, 129-133(1990)
[4] Erdős, P., Tuza, Z.: Vertex coverings of the edge set in a connected graph. Graph Theory, Combinatorics, and Applications. 1179-1187(1995)
[5] Chvátal, V., McDiarmid, C.: Small transversals in hypergraphs. Combinatorica. 12, 19-26(1992)
[6] Henning, M.A., LőWenstein, C.: Hypergraphs with large transversal number and with edge sizes at least four. Discrete Appl. Math. 10(3), 1133-1140(2012)
[7] Dorfling, M., Henning, M.A.: Linear hypergraphs with large transversal number and maximum degree two. Eur. J. Comb. 36, 231-236(2014)
[8] Thomassè, S., Yeo, A.: Total domination of graphs and small transversals of hypergraphs. Combinatorica. 27, 473-487(2007)
[9] Henning, M.A., Yeo, A.: Hypergraphs with large transversal number. Discrete Math. 313, 959-966(2013)
[10] Henning, M. A., Yeo, A.: Transversals in 4-Uniform Hypergraphs. Electronic J. Comb. 23(3), #P.50(2015)
[11] Henning,M.A., Rad, N.J.: A note on improved upper bounds on the transversal number of hypergraphs. Discrete Mathematics Algorithms and Applications. 11(2), 1950004(2019)
[12] Henning, M.A., Yeo, A.: Affine Planes and Transversals in 3-Uniform Linear Hypergraphs. Graphs Combin. 37(6), 867-890(2021)
[13] Diao, Z.: On the Vertex Cover Number of 3-Uniform Hypergraph. J. Oper. Res. Soc. China. 9, 427-440(2021)
[14] Berge, C.: Hypergraphs: Combinatorics of Finite Sets. Elsevier, New York (1989)
