NDA@SZTAKI

Bounds on the Number of Edges in Hypertrees

Katona, Gyula Y.

SzabĂł, PĂ©ter

North-Holland Publishing Company

2016

QA166-QA166.245 Graphs theory / gráfelmélet

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.

angol

Article

PeerReviewed

info:eu-repo/semantics/article

text

http://real.mtak.hu/39327/1/katona_szabo_jav4_u.pdf

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

http://real.mtak.hu/39327/

http://dx.doi.org/10.1016/j.disc.2016.01.004

MTMT:3044684; doi:10.1016/j.disc.2016.01.004