Improved Encoding and Counting of Uniform Hypertrees

Abstract

We consider labeled $r$-uniform hypertrees having $n\ge r\ge 2$ vertices. The number of hyperedges in such a hypertree is $m=(n-1)/(r-1)$. We show that there are exactly $f(n,r)=\frac{(n-1)!n^{m-1}}{(r-1){!}^{m}m!}$ $r$-uniform hypertrees with $n$ vertices labeled with distinct integers. We also give an encoding scheme that encodes such hypertrees using, on an average, at most $1+{\log }_{2}e$ bits more than ${\log }_2(f(n,r))$.

Withdrawn due to discovery of a prior work by Lavault [1] which contains the encoding and decoding algorithms described in section 2 of our work. In section 3, we fill in some details required to make the encoding scheme near-optimal, which makes the running time $\tilde{O}(n^2)$. [1] C. Lavault. A note on Prüfer-like coding and counting forests of uniform hypertrees. CSIT 2011, pp.82-85