Previous |  Up |  Next

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: 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
.

Files

Files Size Format View
CzechMathJ_72-2022-2_4.pdf 167.2Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo