Geodesic
The relation between the number of leaves of a tree and its diameter
Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 365-369

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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)=\lceil 2(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.
DOI : 10.21136/CMJ.2021.0492-20
Classification : 05C05, 05C12, 05C35
Keywords: leaf; diameter; tree; spider 
@article{10_21136_CMJ_2021_0492_20,
     author = {Qiao, Pu and Zhan, Xingzhi},
     title = {The relation between the number of leaves  of a tree and its diameter},
     journal = {Czechoslovak Mathematical Journal},
     pages = {365--369},
     publisher = {mathdoc},
     volume = {72},
     number = {2},
     year = {2022},
     doi = {10.21136/CMJ.2021.0492-20},
     mrnumber = {4412764},
     zbl = {07547209},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0492-20/}
}
TY  - JOUR
AU  - Qiao, Pu
AU  - Zhan, Xingzhi
TI  - The relation between the number of leaves  of a tree and its diameter
JO  - Czechoslovak Mathematical Journal
PY  - 2022
SP  - 365
EP  - 369
VL  - 72
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0492-20/
DO  - 10.21136/CMJ.2021.0492-20
LA  - en
ID  - 10_21136_CMJ_2021_0492_20
ER  - 
%0 Journal Article
%A Qiao, Pu
%A Zhan, Xingzhi
%T The relation between the number of leaves  of a tree and its diameter
%J Czechoslovak Mathematical Journal
%D 2022
%P 365-369
%V 72
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0492-20/
%R 10.21136/CMJ.2021.0492-20
%G en
%F 10_21136_CMJ_2021_0492_20
Qiao, Pu; Zhan, Xingzhi. The relation between the number of leaves  of a tree and its diameter. Czechoslovak Mathematical Journal, Tome 72 (2022) no. 2, pp. 365-369. doi: 10.21136/CMJ.2021.0492-20

Cité par Sources :