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

被引：2

作者：

Qiao, Pu ^{[1
]}

Zhan, Xingzhi ^{[2
]}

机构：

[1] East China Univ Sci & Technol, Dept Math, 130 Meilong Rd, Shanghai 200237, Peoples R China

[2] East China Normal Univ, Dept Math, 500 Dongchuan Rd, Shanghai 200241, Peoples R China

来源：

CZECHOSLOVAK MATHEMATICAL JOURNAL | 2022年 / 72卷 / 02期

关键词：

leaf; diameter; tree; spider;

D O I：

10.21136/CMJ.2021.0492-20

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：365 / 369

页数：5