A Toughness Condition for a Spanning Tree With Bounded Total Excesses.

Let $$k$$ be an integer with $$k \ge 2$$ . In terms of the toughness of a graph, Win gave a sufficient condition for the existence of a spanning $$k$$ -tree, that is, a spanning tree in which the maximum degree is at most $$k$$ . For a spanning tree $$T$$ of a graph $$G$$ , we define the total excess $$\mathrm{te}(T,k)$$ of $$T$$ from $$k$$ as $$\mathrm{te}(T,k) := \sum _{v \in V(T)} \max \{d_T(v)-k, 0\}$$ , where $$V(T)$$ is the vertex set of $$T$$ and $$d_T(v)$$ is the degree of a vertex $$v$$ in $$T$$ . Enomoto, Ohnishi and Ota extended Win's result by giving a condition that guarantees the existence of a spanning tree $$T$$ with a bounded total excess. Here we further extend the result as follows. Let $$\omega (G)$$ be the number of components of a graph $$G$$ . Let $$k_1,k_2, \ldots ,k_p$$ be $$p$$ integers with $$k_1 \ge k_2 \ge \cdots \ge k_p \ge 2$$ , let $$t_1,t_2, \ldots ,t_p$$ be $$p$$ nonnegative integers, and let $$G$$ be a connected graph. If $$G$$ satisfies that $$\omega (G-S) \le (k_i - 2)|S| + 2 +t_i$$ for every $$1 \le i \le p$$ and every $$S \subset V(G)$$ , then $$G$$ has a spanning tree $$T$$ such that $$\mathrm{te}(T,k_i) \le t_i$$ for every $$1 \le i \le p$$ . [ABSTRACT FROM AUTHOR]