Loading...
Loading...

Go to the content (press return)

Almost every tree with m edges decomposes K2m,2m

Author
Drmota, M.; Llado, A.
Type of activity
Journal article
Journal
Combinatorics probability and computing
Date of publication
2014-01
Volume
23
Number
1
First page
50
Last page
65
DOI
https://doi.org/10.1017/S0963548313000485 Open in new window
Project funding
COMBINATÒRIA , TEORIA DE GRAFS I APLICACIONS
Optimización y problemas extremales en teoria de grafos y combinatoria. Aplicacions a les redes de comunicación
Repository
http://hdl.handle.net/2117/28488 Open in new window
URL
http://journals.cambridge.org/action/displayAbstract?aid=9098773 Open in new window
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.
Citation
Drmota, M.; Llado, A. Almost every tree with m edges decomposes K2m,2m. "Combinatorics probability and computing", Gener 2014, vol. 23, núm. 1, p. 50-65.
Keywords
Bipartition, Complete bipartite graphs, Complete graphs, Equal sizes, Random tree
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Attachments