The relation between the number of leaves of a tree and its diameter

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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) = ⌈2(n − 1)/d⌉ 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.

Original languageEnglish
Pages (from-to)365-369
Number of pages5
JournalCzechoslovak Mathematical Journal
Volume72
Issue number2
DOIs
StatePublished - Jun 2022

Keywords

  • 05C05
  • 05C12
  • 05C35
  • diameter
  • leaf
  • spider
  • tree

Cite this