Home>Results

  • Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

[期刊论文]

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

Share
Edit Delete 报错

author:

Chen, Z.-A. (Chen, Z.-A..) [1] | Chen, B. (Chen, B..) [2]

Indexed by:

Scopus

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:

05C65 05C70 k-uniform hypergraph Perfect matching Transversal number

Community:

  • [ 1 ] [Chen Z.-A.]Center for Discrete Mathematics, Fuzhou University, Fujian, Fuzhou, 350108, China
  • [ 2 ] [Chen B.]Center for Discrete Mathematics, Fuzhou University, Fujian, Fuzhou, 350108, China

Reprint 's Address:

Show more details

Related Article:

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

CAS Journal Grade:4

Cited Count:

WoS CC Cited Count:

30 Days PV: 1

Online/Total:122/10270435
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1