Relation between the number of leaves of a tree and its diameter

arXiv1904.12150MaRDI QIDQ6317850FDOQ6317850

Authors: Pu Qiao, Xingzhi Zhan 

Publication date: 27 April 2019

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)=lceil2(n-1)/dceil$ 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 $dge2,$ $L(n,d)=leftlceilfrac2(n-1)dightceil$ if $d$ is even and $L(n,d)=leftlceilfrac2(n-2)d-1ightceil$ 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+3lenle(k+1)f+1.$

This page was built for publication: Relation between the number of leaves of a tree and its diameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6317850)