Almost Every Tree With m Edges Decomposes K2m, 2m. (3rd December 2013) - DRMOTA, M.; LLADÓ, A.
Abstract : We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K 2 m, 2 m, a result connected to a conjecture of Graham and Häggkvist. The result also implies that asymptotically almost surely a tree with m edges decomposes the complete graph with O ( m 2 ) edges. An ingredient of the proof consists in showing that the bipartition classes of the base tree of a random tree have roughly equal size.