A NOTE ON TOTAL EXCESS OF SPANNING TREES

A graph G is said to be t- tough if |S| <= t center dot omega(G - S) for any subset S of V (G) with.(G - S) >= 2, where omega(G - S) is the number of components in G - S. Win proved that for any integer n >= 3 every 1/n-2 -tough graph has a spanning tree with maximum degree at most n. In this paper, we investigate t-tough graphs including the cases where t is not an element of {1, 1/2, 1/3,...}, and consider spanning trees in such graphs. Using the notion of total excess, we prove that if G is 1-epsilon/n-2+epsilon - tough for an integer n >= 2 and a real number e with 2 /|V(G)| <= epsilon <= 1, then G has a spanning tree T such that S (v subset of V(G)) max{0, deg(T) (v) - n} <= epsilon|V(G)| - 2. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, epsilon). As a consequence, we prove the existence of "a universal tree" in a connected t-tough graph G, that is a spanning tree T such that Sigma (v is an element of V(T)) max{0, deg(T) (v) - n} <= epsilon|V(G)| - 2 for any integer n >= 2 and real number epsilon with 2/ |V(G)| <= epsilon <= 1, which satisfy t >= 1-epsilon/n-2+epsilon.