Bounds on the Number of Edges in Hypertrees

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


Download (299kB) | Preview


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 cycle-free property holds. An edge-minimal 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-(k-1)$ edges if $n>n_0(k)$, and it has at most $\binom{n}{k-1}$ edges. The latter bound is asymptotically sharp in 3-uniform case.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
Depositing User: MTMT SWORD
Date Deposited: 05 Sep 2016 14:06
Last Modified: 05 Sep 2016 14:06

Actions (login required)

Edit Item Edit Item