Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
复制标题
图中最小度数为三的具有许多叶子的生成树
DOI：
--
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
P. Bonsma
中科院分区：
文献类型：
--
作者：
P. Bonsma
我们为图表的所有跨越树的最大叶子数量提供了两个下限。对于$ n $顶点上的连接的，无三角形的图形，至少三个，我们表明存在至少$（n+4）/3 $叶子的生成树。对于最低度至少三个的连接图，没有第三度的顶点引起的钻石，我们表明存在至少$（2n+12）/7 $叶子的生成树。 （钻石是$ k_4 $减去一个边缘。）证据使用的事实是，跨越了许多叶子的树木对应于小型连接的主导套件。这两个界限最适合其各自的图形类别。对于这两个边界，都给出了跨越满足边界的简单多项式时间算法。
We present two lower bounds for the maximum number of leaves over all spanning trees of a graph. For connected, triangle-free graphs on $n$ vertices, with minimum degree at least three, we show that a spanning tree with at least $(n+4)/3$ leaves exists. For connected graphs with minimum degree at least three, without diamonds induced by vertices of degree three, we show that a spanning tree with at least $(2n+12)/7$ leaves exists. (A diamond is a $K_4$ minus one edge.) The proofs use the fact that spanning trees with many leaves correspond to small connected dominating sets. Both of these bounds are best possible for their respective graph classes. For both bounds, simple polynomial time algorithms that find spanning trees satisfying the bounds are given.