Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
leaf; diameter; tree; spider
leaf; diameter; tree; spider
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.
References:
[1] Lesniak, L.: On longest paths in connected graphs. Fundam. Math. 86 (1975), 283-286. DOI 10.4064/fm-86-3-283-286 | MR 0396330 | Zbl 0293.05141
[2] Ore, O.: Theory of Graphs. Colloquium Publications 38. American Mathematical Society, Providence (1962). DOI 10.1090/coll/038 | MR 0150753 | Zbl 0105.35401
[3] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
Search
Partner of
