Article
| 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: | 2022-09-08 |
| 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 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
