Back to Search
Start Over
Almost every tree with m edges decomposes K2m,2m
- Publication Year :
- 2014
-
Abstract
- We show that asymptotically almost surely a tree with m edges decomposes the complete bipartite graph K2m,2m, 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(m2) 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. © Cambridge University Press 2013.<br />Peer Reviewed<br />Postprint (author’s final draft)
Details
- Database :
- OAIster
- Notes :
- 16 p., application/pdf, English
- Publication Type :
- Electronic Resource
- Accession number :
- edsoai.ocn926959521
- Document Type :
- Electronic Resource