Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (3): 829-835.doi: 10.1007/s40305-022-00445-1

Previous Articles     Next Articles

An Upper Bound for the Transversal Number of Connected k-Uniform Hypergraphs

Zi-An Chen, Bin Chen   

  1. Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108, Fujian, China
  • Received:2022-04-15 Revised:2022-09-03 Online:2024-09-30 Published:2024-08-15
  • Contact: Zi-An Chen, Bin Chen E-mail:michaelchen24@163.com;cbfzu03@163.com
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (No. 12171089).

Abstract: 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.

Key words: Transversal number, k-uniform hypergraph, Perfect matching

CLC Number: