Almost Every Tree With m Edges Decomposes K2m, 2m. (3rd December 2013)

• Record Type: Journal Article
• Authors: DRMOTA, M.; LLADÓ, A.
• Is Part Of: Combinatorics, probability and computing. Volume 23:Number 1(2014:Jan.)
• Page Start: 50
• Page End: 65
• Publication Date: 2013-12-03
• Subjects: Primary 05C51, -- Secondary 05C80; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548313000485
• Languages: English
• ISSNs: 0963-5483

Abstract

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.