Bounds on isoperimetric values of trees

AbstractLet G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as be(i,G)=minS⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as be(G)=max1≤j≤|V|be(j,G). Let bv(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) 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