Loading...
Loading...

Go to the content (press return)

Decomposing almost complete graphs by random trees

Author
Llado, A.
Type of activity
Journal article
Journal
Journal of combinatorial theory. Series A
Date of publication
2018-02
Volume
154
First page
406
Last page
421
DOI
10.1016/j.jcta.2017.09.008
Repository
http://hdl.handle.net/2117/117218 Open in new window
URL
http://www.sciencedirect.com/science/article/pii/S0097316517301322?via%3Dihub Open in new window
Abstract
An old conjecture of Ringel states that every tree with m edges decomposes the complete graph K2m+1. The best known lower bound for the order of a complete graph which admits a decomposition by every given tree with m edges is O(m3). We show that asymptotically almost surely a random tree with m edges and p=2m+1 a prime decomposes K2m+1(r) for every r=2, the graph obtained from the complete graph K2m+1 by replacing each vertex by a coclique of order r. Based on this result we show, among other r...
Citation
Llado, A. Decomposing almost complete graphs by random trees. "Journal of combinatorial theory. Series A", Febrer 2018, vol. 154, p. 406-421.
Keywords
Graph decomposition, Polynomial method, Ringel's conjecture
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants