TY - JOUR
T1 - The relation between the number of leaves of a tree and its diameter
AU - Qiao, Pu
AU - Zhan, Xingzhi
N1 - Publisher Copyright:
© 2021, Institute of Mathematics, Czech Academy of Sciences.
PY - 2022/6
Y1 - 2022/6
N2 - 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) = ⌈2(n − 1)/d⌉ 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.
AB - 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) = ⌈2(n − 1)/d⌉ 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.
KW - 05C05
KW - 05C12
KW - 05C35
KW - diameter
KW - leaf
KW - spider
KW - tree
UR - https://www.scopus.com/pages/publications/85117838918
U2 - 10.21136/CMJ.2021.0492-20
DO - 10.21136/CMJ.2021.0492-20
M3 - 文章
AN - SCOPUS:85117838918
SN - 0011-4642
VL - 72
SP - 365
EP - 369
JO - Czechoslovak Mathematical Journal
JF - Czechoslovak Mathematical Journal
IS - 2
ER -