Spanning trees with few branch vertices
Spanning trees with few branch vertices
复制标题
DOI：
10.1137/17m1152759
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Louis DeBiasio;A. Lo
中科院分区：
文献类型：
--
作者：
Louis DeBiasio;A. Lo
树中的分支顶点是度至少为3的顶点。我们证明了，对所有的$s\geq 1$，每一个最小度至少为$（\frac{1}{s+3}+o（1））n$的n$个顶点的连通图都包含一棵至多有$s$分支顶点的生成树.渐近地，这是最好的可能性，并解决了，在不太一般的形式，Flandrin，Kaiser，Kuuzel，Li和Ryjaucek的问题，这最初是由光网络的设计中的优化问题的动机。
A branch vertex in a tree is a vertex of degree at least three. We prove that, for all $s\geq 1$, every connected graph on $n$ vertices with minimum degree at least $(\frac{1}{s+3}+o(1))n$ contains a spanning tree having at most $s$ branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kuuzel, Li and Ryjaucek, which was originally motivated by an optimization problem in the design of optical networks.