Relation between the number of leaves of a tree and its diameter
read the original abstract
Let $L(n,d)$ denote the minimum possible number of leaves in a tree of order $n$ and diameter $d.$ In 1975 Lesniak 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.$ We prove that for $d\ge 2,$ $ L(n,d)=\left\lceil \frac{2(n-1)}{d}\right\rceil$ if $d$ is even and $L(n,d)=\left\lceil \frac{2(n-2)}{d-1}\right\rceil$ if $d$ is odd. The converse problem is also considered. Let $D(n,f)$ be the minimum possible diameter of a tree of order $n$ with exactly $f$ leaves. We prove that $D(n,f)=2$ if $n=f+1,$ $D(n,f)=2k+1$ if $n=kf+2,$ and $D(n,f)=2k+2$ if $kf+3\le n\le (k+1)f+1.$
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Obstructions for Minor-Closed Classes of limiting Densities Below 3/2
For every δ < 3/2 the ⊆-minimal minor-closed classes with density >δ form a finite explicitly identified set, yielding a 2^poly(n)-time algorithm that computes δ(excl(Z)) or reports ≥3/2 for any finite forbidden-minor set Z.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.