Spanning Trees with Bounded Total Excess

Abstract

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\setminus S)\le (k–2)|S|+2,\text{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,de{g}_T(v)–k\}$. The total $k$-excess $te(T,k)$ is the summation of the $k$-excesses of all vertices, namely,
$$te(T,k)=\sum _{v\in V(T)}max\{0,de{g}_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\ge 2$, $b\ge 0$, and $G$ is a connected graph satisfying the following condition:
$$\text{for every subset S of V(G)},c(G\setminus S)\le (k–2)|S|+2+b.$$
Then, $G$ has a spanning tree with total $k$-excess at most $b$.