Bounds on isoperimetric values of trees

The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as Td2), c1d≤be(Td2)≤d and c2d≤bv(Td2)≤d where c1, c2 are constants. For a complete t-ary tree of depth d (denoted as Tdt) and d≥clogt where c is a constant, we show that c1td≤be(Tdt)≤td and c2dt≤bv(Tdt)≤d where c1, c2 are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ℓ(k)=|{i∈N:1≤i≤|V|,be(i,G)≤k}|. We show that ℓ(k)≤22η+kk.