The Relation between the Number of Leaves of a Tree and Its Diameter

摘要

Let L(n, d) denote the minimum possible number of leaves in a tree of order n and diameter d. Lesniak (1975) gave the lower bound B(n,d) = left ceiling 2(n - 1)/d right ceiling for L(n,d). When d is even, B(n,d) = L(n,d). But when d is odd, B(n,d) is smaller than L(n,d) in general. For example, B(21, 3) = 14 while L(21, 3) = 19. In this note, we determine L(n, d) using new ideas. We also consider the converse problem and determine the minimum possible diameter of a tree with given order and number of leaves.

关键词