Czechoslovak Mathematical Journal, Vol. 72, No. 2, pp. 365-369, 2022
The relation between the number of leaves of a tree and its diameter
Pu Qiao, Xingzhi Zhan
Received November 12, 2020. Published online September 7, 2021.
Abstract: 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)=\lceil2(n-1)/d\rceil$ 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.
Affiliations: Pu Qiao, Department of Mathematics, East China University of Science and Technology, 130 Meilong Rd, Xuhui District, Shanghai 200237, P. R. China, e-mail: pq@ecust.edu.cn; Xingzhi Zhan (corresponding author), Department of Mathematics, East China Normal University, 500 Dongchuan Rd., Shanghai 200241, P. R. China, e-mail: zhan@math.ecnu.edu.cn
