Loading...
Loading...

Go to the content (press return)

Decomposing almost complete graphs by random trees

Author
Llado, A.
Type of activity
Journal article
Journal
Electronic notes in discrete mathematics
Date of publication
2014-09-08
Volume
46
First page
177
Last page
183
DOI
https://doi.org/10.1016/j.endm.2014.08.024 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S1571065314000250 Open in new window
Abstract
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...
Keywords
Graph decompositions, Ringel conjecture
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants