The topological trees with extreme Matula numbers

Abstract

Denote by \( p_m \) the \( m \)-th prime number (\( p_1 = 2 \), \( p_2 = 3 \), \( p_3 = 5 \), \( p_4 = 7 \), \dots). Let \( T \) be a rooted tree with branches \( T_1, T_2, \dots, T_r \). The Matula number \( M(T) \) of \( T \) is \( p_{M(T_1)} \cdot p_{M(T_2)} \cdots p_{M(T_r)} \), starting with \( M(K_1) = 1 \). This number was put forward half a century ago by the American mathematician David Matula. In this paper, we prove that the star (consisting of a root and leaves attached to it) and the binary caterpillar (a binary tree whose internal vertices form a path starting at the root) have the smallest and greatest Matula number, respectively, over all topological trees (rooted trees without vertices of outdegree 1) with a prescribed number of leaves – the extreme values are also derived.