Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Almost every tree with m edges decomposes K2m,2m

Autor
Drmota, M.; Llado, A.
Tipus d'activitat
Article en revista
Revista
Combinatorics probability and computing
Data de publicació
2014-01
Volum
23
Número
1
Pàgina inicial
50
Pàgina final
65
DOI
https://doi.org/10.1017/S0963548313000485 Obrir en finestra nova
Projecte finançador
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
Repositori
http://hdl.handle.net/2117/28488 Obrir en finestra nova
URL
http://journals.cambridge.org/action/displayAbstract?aid=9098773 Obrir en finestra nova
Resum
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.
Citació
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.
Paraules clau
Bipartition, Complete bipartite graphs, Complete graphs, Equal sizes, Random tree
Grup de recerca
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants

Arxius