Bounds On Isoperimetric Values of Trees

Abstract

Let G = (V,E) be a finite, simple and undirected graph. For $S\subseteq V$, let $δ(S,G) = \{(u,v) \in E : u \in S \mbox {and} v \in V-S \}$ be the edge boundary of $S$. Given an integer $i$, $1\le i\le |V|$, let the edge isoperimetric value of $G$ at $i$ be defined as $b_e(i,G)={\min }_{S\subseteq V;|S|=i}|\delta (S,G)|$. The edge isoperimetric peak of $G$ is defined as $b_e(G)={\max }_{1\le j\le |V|}{b}_e(j,G)$. Let $b_v(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 \cite{OatYam}. In this paper we provide bounds which improve those in \cite{OatYam}. We show that for a complete binary tree of depth $d$ (denoted as $T_d^2$), $c_{1}d\le b_e(T_d^2)\le d$ and $c_{2}d\le b_v(T_d^2)\le d$ where $c_1$, $c_2$ are constants. For a complete $t$-ary tree of depth $d$ (denoted as $T_d^t$) and $d\ge c\log t$ where $c$ is a constant, we show that $c_1\sqrt{t}d\le b_e(T_d^t)\le td$ and $c_2\frac{d}{\sqrt{t}}\le b_v(T_d^t)\le d$ where $c_1$, $c_2$ are constants. Our results are generalized to arbitrary(rooted) trees.

18 pages