Almost every tree with m edges decomposes K2m,2m

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/28488

Título:	Almost every tree with m edges decomposes K2m,2m
Autor/a:	Drmota, Michael; Lladó Sánchez, Ana M.
Otros autores:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
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.
Abstract:	Peer Reviewed
Materia(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -Bipartition -Complete bipartite graphs -Complete graphs -Equal sizes -Random tree -Grafs, Teoria de -05C Graph theory
Derechos:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipo de documento:	Artículo - Versión presentada Artículo
Compartir: