Katona, Gyula Y. and Szabó, Péter (2016) Bounds on the Number of Edges in Hypertrees. DISCRETE MATHEMATICS, 339 (7). pp. 18841991. ISSN 0012365X

Text
katona_szabo_jav4_u.pdf Download (299kB)  Preview 
Abstract
Let $\mathcal{H}$ be a $k$uniform hypergraph. A chain in $\mathcal{H}$ is a sequence of its vertices such that every $k$ consecutive vertices form an edge. In 1999 Katona and Kierstead suggested to use chains in hypergraphs as the generalisation of paths. Although a number of results have been published on Hamiltonian chains in recent years, the generalisation of trees with chains has still remained an open area. We generalise the concept of trees for uniform hypergraphs. We say that a $k$uniform hypergraph $\mathcal{H}$ is a hypertree if every two vertices of $\mathcal{H}$ are connected by a chain, and an appropriate kind of cyclefree property holds. An edgeminimal hypertree is a hypertree whose edge set is minimal with respect to inclusion. After considering these definitions, we show that a $k$uniform hypertree on $n$ vertices has at least $n(k1)$ edges if $n>n_0(k)$, and it has at most $\binom{n}{k1}$ edges. The latter bound is asymptotically sharp in 3uniform case.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.245 Graphs theory / gráfelmélet 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  05 Sep 2016 14:06 
Last Modified:  05 Sep 2016 14:06 
URI:  http://real.mtak.hu/id/eprint/39327 
Actions (login required)
Edit Item 