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

Zitieren

Zitierform:

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

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export