Decomposing almost complete graphs by random trees

Abstract

An old conjecture of Ringel states that every tree with m edges decomposes the complete graph Krm+1 for each r≥2 provided that r and m+1 are not both odd. The best lower bound for the order of a complete graph decomposed by a given tree with m edge 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.

Locations

• arXiv (Cornell University) - View - PDF
• RECERCAT (Consorci de Serveis Universitaris de Catalunya) - View - PDF
• UPCommons institutional repository (Universitat Politècnica de Catalunya) - View - PDF
• Electronic Notes in Discrete Mathematics - View