Purely Heterogeneous Spanning Tree Decompositions

Abstract

Decompositions of complete or near-complete graphs into spanning trees have been widely studied, but usually in the homogeneous case, where all component trees are isomorphic. A spanning tree decomposition $\mathcal{T}=(T_1,\dots ,T_n)$ of such a graph is purely heterogeneous if no two trees $T_i$ are isomorphic. We show existence of such decompositions with the maximum degree condition $\mathrm{\Delta }(T_i)=i+1$ for each $i\in [1..n]$, for every largest possible graph of odd order, and every even order graph which is the complement of a spanning tree satisfying a necessary maximum degree condition.