| Title:
|
The relation between the number of leaves of a tree and its diameter (English) |
| Author:
|
Qiao, Pu |
| Author:
|
Zhan, Xingzhi |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
72 |
| Issue:
|
2 |
| Year:
|
2022 |
| Pages:
|
365-369 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
leaf |
| Keyword:
|
diameter |
| Keyword:
|
tree |
| Keyword:
|
spider |
| MSC:
|
05C05 |
| MSC:
|
05C12 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 07547209 |
| idMR:
|
MR4412764 |
| DOI:
|
10.21136/CMJ.2021.0492-20 |
| . |
| Date available:
|
2022-04-21T18:59:40Z |
| Last updated:
|
2024-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/150406 |
| . |
| Reference:
|
[1] Lesniak, L.: On longest paths in connected graphs.Fundam. Math. 86 (1975), 283-286. Zbl 0293.05141, MR 0396330, 10.4064/fm-86-3-283-286 |
| Reference:
|
[2] Ore, O.: Theory of Graphs.Colloquium Publications 38. American Mathematical Society, Providence (1962). Zbl 0105.35401, MR 0150753, 10.1090/coll/038 |
| Reference:
|
[3] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| . |
