Decomposing almost complete graphs by random trees

Abstract: An old conjecture of Ringel states that every tree with

m

edges decomposes the complete graph

K_{2 m + 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 (m^{3})

. We show that asymptotically almost surely a random tree with

m

edges and

p = 2 m + 1

a prime decomposes

K_{2 m + 1} (r)

for every

r g e 2

, the graph obtained from the complete graph

K_{2 m + 1}

by replacing each vertex by a coclique of order

r

. Based on this result we show, among other results, that a random tree with

m + 1

edges a.a.s. decomposes the compete graph

K_{6 m + 5}

minus one edge.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Decomposing almost complete graphs by random trees