Loading...
Loading...

Go to the content (press return)

Decomposing almost complete graphs by random trees

Author
Llado, A.
Type of activity
Presentation of work at congresses
Name of edition
IX Jornadas de Matemática Discreta y Algorítmica
Date of publication
2014
Presentation's date
2014-07-07
Book of congress proceedings
IX Jornadas de Matemática Discreta y Algorítmica : Tarragona, 7-9 de Julio de 2014
First page
383
Last page
388
Repository
http://hdl.handle.net/2117/27908 Open in new window
Abstract
An old conjecture of Ringel states that every tree with m edges decom- poses the complete graph K 2 m +1 . A more general version of the Ringel’s conjecture says that every tree with m edges decomposes K rm +1 for each r = 2 provided that r and m + 1 are not both odd. The best lower bound for the order of a complete graph decomposed by a given tree with m edge is O ( m 3 ). We show that asymptotically almost surely a random tree with m edges and p = 2 m + 1 is a prime decomposes the complete g...
Citation
Llado, A. Decomposing almost complete graphs by random trees. A: Jornadas de Matemática Discreta y Algorítmica. "IX Jornadas de Matemática Discreta y Algorítmica : Tarragona, 7-9 de Julio de 2014". Tarragona: 2014, p. 383-388.
Keywords
Ringel Conjecture, random trees
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants