# On spanning tree congestion

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.)

### Zitieren

Zitierform:

Löwenstein, Christian / Rautenbach, Dieter / Regen, Friedrich: On spanning tree congestion. 2008.

### Zugriffsstatistik

Gesamt:
Volltextzugriffe: