Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Decomposing almost complete graphs by random trees

Autor
Llado, A.
Tipus d'activitat
Article en revista
Revista
Electronic notes in discrete mathematics
Data de publicació
2014-09-08
Volum
46
Pàgina inicial
177
Pàgina final
183
DOI
https://doi.org/10.1016/j.endm.2014.08.024 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S1571065314000250 Obrir en finestra nova
Resum
An old conjecture of Ringel states that every tree with m edges decomposes the complete graph Krm+1Krm+1 for each r=2r=2 provided that r and m+1m+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(m3)O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1p=2m+1 a prime decomposes K2m+1(r)K2m+1(r) for every r=2r=2, the graph obtained from the complete graph K2m+1K2m+1 by replacing each vertex by a c...
Paraules clau
Graph decompositions, Ringel conjecture
Grup de recerca
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants