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

• • 上一篇    下一篇

  

  • 收稿日期:2022-04-15 修回日期:2022-09-03 出版日期:2024-09-30 发布日期:2024-08-15
  • 通讯作者: Zi-An Chen, Bin Chen E-mail:michaelchen24@163.com;cbfzu03@163.com

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

中图分类号: