Minimal trees of given search number (Q580350)

In this paper, a tree of given search number is called minimal if it has the least possible number of vertices amongst all such trees. Let \(T_ 3(k)\) denote the set of all isomorphism classes of minimal trees with given search number \(k>0.\) In this paper it is proved that \(| T_ 3(k)| =\left( \begin{matrix} p_{k-1}(O)+2\\ 3\end{matrix} \right)\), where \(\{p_ k(x)\}_{k\geq 1}\) is a family of polynomials defined recursively and ln ln\(| T_ 3(k)| \sim k \ln 3\) as \(k\to \infty\). In addition, a language for describing these trees and structures within them is developed. Some properties of the automorphisms group of the generic representative of a member of \(T_ 3(k)\) are discussed.