The Bounds of the Edge Number in Generalized Hypertrees

Ke Zhang, Haixing Zhao, Zhonglin Ye, Yu Zhu and Liang Wei
Additional contact information
Ke Zhang: School of Computer, Qinghai Normal University, Xining 810008, China
Haixing Zhao: School of Computer, Qinghai Normal University, Xining 810008, China
Zhonglin Ye: Key Laboratory of Tibetan Information Processing and Machine Translation in QH, Xining 810008, China
Yu Zhu: School of Computer, Qinghai Normal University, Xining 810008, China
Liang Wei: School of mathematics and statistics, Qinghai Normal University, Xining 810008, China

Mathematics, 2018, vol. 7, issue 1, 1-10

Abstract: A hypergraph H = ( V , ε ) is a pair consisting of a vertex set V , and a set ε of subsets (the hyperedges of H ) of V . A hypergraph H is r -uniform if all the hyperedges of H have the same cardinality r . Let H be an r -uniform hypergraph, we generalize the concept of trees for r -uniform hypergraphs. We say that an r -uniform hypergraph H is a generalized hypertree ( G H T ) if H is disconnected after removing any hyperedge E , and the number of components of G H T − E is a fixed value k ( 2 ≤ k ≤ r ) . We focus on the case that G H T − E has exactly two components. An edge-minimal G H T is a G H T whose edge set is minimal with respect to inclusion. After considering these definitions, we show that an r -uniform G H T on n vertices has at least 2 n / ( r + 1 ) edges and it has at most n − r + 1 edges if r ≥ 3 and n ≥ 3 , and the lower and upper bounds on the edge number are sharp. We then discuss the case that G H T − E has exactly k ( 2 ≤ k ≤ r − 1 ) components.

Keywords: hypergraph; generalized hypertree; bound; component (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/1/2/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/1/2/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2018:i:1:p:2-:d:192026

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().