A note on total excess of spanning trees
Yukichika Ohnishi, Katsuhiro Ota · AKCE International Journal of Graphs and Combinatorics · 2011
A graph G is said to be t-tough if |S| ≥ t ·ω(G−S) for any subset S of V (G) with ω(G − S) ≥ 2, where ω(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 / ∈ {1, 1 2 , 13 , . . .}, and consider spanning trees in such graphs. Using the notion of total excess, we prove that if G is 1−e n−2+e -tough for an integer n ≥ 2 and a real number e with 2 |V (G)| ≤ e ≤ 1, then G has a spanning tree T such that ∑ v∈V (G) max{0,degT (v)− n} ≤ e|V (G)| − 2. ∗Research Fellow of Japan Society for the Promotion Science. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, e). 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 ∑ v∈V (T ) max{0, degT (v)−n} ≤ e|V (G)|−2 for any integer n ≥ 2 and real number e with 2 |V (G)| ≤ e ≤ 1, which satisfy t ≥ 1−e n−2+e .