Bounds On Isoperimetric Values of Trees
| dc.creator | Bharadwaj, B. V. Subramanya | |
| dc.creator | Chandran, L. Sunil | |
| dc.date | 2007-01-21 | |
| dc.date | 2008-01-09 | |
| dc.date.accessioned | 2026-07-07T08:53:22Z | |
| dc.date.available | 2026-07-07T08:53:22Z | |
| dc.description | 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 \leq i \leq | V |$, let the edge isoperimetric value of $G$ at $i$ be defined as $b_e(i,G) = \min_{S \subseteq V; |S| = i} |δ(S,G)|$. The edge isoperimetric peak of $G$ is defined as $b_e(G)=\max_{1 \leq j \leq | 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_1d \leq b_e(T_d^2) \leq d$ and $c_2d \leq b_v(T_d^2) \leq d$ where $c_1$, $c_2$ are constants. For a complete $t$-ary tree of depth $d$ (denoted as $T_d^t$) and $d \geq c\log{t}$ where $c$ is a constant, we show that $c_1\sqrt{t}d \leq b_e(T_d^t) \leq td$ and $c_2\frac{d}{\sqrt{t}} \leq b_v(T_d^t) \leq d$ where $c_1$, $c_2$ are constants. Our results are generalized to arbitrary(rooted) trees. | |
| dc.description | 18 pages | |
| dc.identifier | https://arxiv.org/abs/math/0701587 | |
| dc.identifier | http://arxiv.org/abs/math/0701587 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/145597 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C05 | |
| dc.title | Bounds On Isoperimetric Values of Trees | |
| dc.type | text |