Indexed by:
Abstract:
Let H be a hypergraph with vertex set V(H) and hyperedge set E(H). We call a vertex set R⊆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 2m+13, that is, τ(H)⩽2m+13, where m is the size of H. Moreover, they gave the necessary and sufficient conditions to reach the upper bound, namely τ(H)=2m+13, if and only if H is a hypertree with a perfect matching. In this paper, we investigate the transversal number of connected k-uniform hypergraphs for k⩾3. We confirm that τ(H)⩽(k-1)m+1k for any k-uniform hypergraph H with size m. Furthermore, we show that τ(H)=(k-1)m+1k if and only if H is a hypertree with a perfect matching, which generalizes the results of Diao. © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2022. Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
Journal of the Operations Research Society of China
ISSN: 2194-668X
Year: 2024
Issue: 3
Volume: 12
Page: 829-835
0 . 9 0 0
JCR@2023
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: