On the Cutwidth and the Topological Bandwidth of a Tree
Fan Chung · SIAM Journal on Algebraic and Discrete Methods · 1985
We investigate the relations between the topological bandwidth $b^* ( G )$ and the cutwidth $f ( G )$ for a graph G. We show that for any tree T we have $b^* \leqslant f ( T ) \leqslant b^* ( T ) + \log_2 b^* ( T ) + 2$. These bounds are “almost” best possible, since we will prove that for each n, there exists a tree $T_n $ such that $b^* ( T_n ) = n$ and $f ( T_n ) \geqslant n + \log_2 n - 1$, and the star $S_{2n} $ with 2n edges satisfies $b^* ( S_{2n} ) = f ( S_{2n} ) = n$.