On spanning tree congestion

Löwenstein, Christian; Rautenbach, Dieter GND; Regen, Friedrich GND

We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge-cut defined in G by the vertex sets of the two components of T - e contains at most n^{\frac{3}{2}} many edges which solves a problem posed by Ostrovskii (Minimal congestion trees, Discrete Math. 285 (2004), 219-226.)


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved