Spanning Trees with Bounded Total Excess

作者：Enomoto Hikoe^*; Ohnishi Yukichika; Ota Katsuhiro

来源：Ars Combinatoria, 2011, 102: 289-295.

Let c(H) denote the number of components of a graph H. Win proved in 1989 that if a connected graph G satisfies
c(G\S) <= (k - 2)vertical bar S vertical bar + 2, for every subset S of V(G),
then G has a spanning tree with maximum degree at most k.
For a spanning tree T of a connected graph, the k-excess of a vertex v is defined to be max{0, deg(T)(v) - k}. The total k-excess te(T, k) is the summation of the k-excesses of all vertices, namely,
te(T, k) = Sigma(v is an element of V(T)) max{0, deg(T)(v) - k}.
This paper gives a sufficient condition for a graph to have a spanning tree with bounded total k-excess. Our main result is as follows.
Suppose k >= 2, b >= 0, and G is a connected graph satisfying the following condition:
For every subset S of V(G), c(G\S) <= (k - 2)vertical bar S vertical bar + 2 + b.
Then, G has a spanning tree with total k-excess at most b.

• 出版日期2011-10