Let K_n~((r)) be the order n uniform complete multigraph with edge multiplicity r. A spanning tree decomposition of K_n~((r)) partitions its edge set into a family T of edge-induced spanning trees. In a purely heterogeneous decomposition T no trees are isomorphic. Every order n tree occurs in a fully heterogeneous decomposition T. All trees have equal multiplicity in a balanced decomposition T. We say that T is reducible if it has a proper subfamily T' ? T such that T' is a spanning tree decomposition of K_n~((s)) for some s with r > s >0. We show that for fixed n and sufficiently large r, every decomposition of K_n~((r)) is reducible. We also show that when n ≥ 6, K_n~((2)) has a purely heterogeneous decomposition T comprising a path, three trees of maximum degree Δ = 3, and one for each Δ > 3.
展开▼
