2015/12/01 by Anna Lladó, Lladó, Anna
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1512.00427
Some typos had been corrected
arxiv created 2015/12/07 · arxiv updated 2015/12/08
An old conjecture of Ringel states that every tree with m edges decomposes the complete graph K2m+1. The best known lower bound for the order of a complete graph which admits a decomposition by every given tree with m edges is O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1 a prime decomposes K2m+1(r) for every r≥ 2, the graph obtained from the complete graph K2m+1 by replacing each vertex by a coclique of order r. Based on this result we show, among other results, that a random tree with m+1 edges a.a.s. decomposes the compete graph K6m+5 minus one edge.