# Article

Full entry | Fulltext not available (moving wall 24 months)
Keywords:
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

Partner of