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

作者：Qiao, Pu; Zhan, Xingzhi^*

来源：CZECHOSLOVAK MATHEMATICAL JOURNAL, 2022, 72(2): 365-369.

DOI：10.21136/CMJ.2021.0492-20

• leaf
• diameter
• tree
• spider

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.

• 单位
  华东理工大学