On a conjecture of Graham and Häggkvist for random trees
Michael Drmota, Anna Lladó · Scuola Normale Superiore eBooks · 2013
A conjecture of Graham and Häggkvist says that every tree with m edges decomposes the complete bipartite graph K m,m . By establishing some properties of random trees with the use of singularity analysis of generating functions, we prove that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K 2 m ,2 m . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.