On spanning tree congestion
On spanning tree congestion
复制标题
关于生成树拥塞
DOI：
10.1016/j.disc.2009.01.012
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Friedrich Regen
中科院分区：
文献类型：
--
作者：
Christian Löwenstein;D. Rautenbach;Friedrich Regen
我们证明每个 n 阶连通图 G 都有一个生成树 T，使得对于 T 的每条边 e，由 T−e 的两个分量的顶点集在 G 中定义的边割最多包含 n32 条边。这一结果解决了 Ostrovskii 提出的问题（M.I. Ostrovskii, Minimal Congestion trees, Discrete Math. 285 (2004) 219–226）。
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 n32edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219–226).