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)