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 τ = (T 1, ..., 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 Δ(T i ) = i+l for each i ⋯ [l..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.