Every tree is a large subtree of a tree that decomposes Kn or Kn,n
MetadataShow full item record
Let T be a tree with m edges. A well-known conjecture of Ringel states that every tree T with m edges decomposes the complete graph K2m+1. Graham and H¨aggkvist conjectured that T also decomposes the complete bipartite graph Km,m. In this paper, we show that there exists an integer n with n d3(m 1)/2e
and a tree T1 with n edges such that T1 decomposes K2n+1 and contains T. We also show that there exists an integer n0 with n0 2m 1 and a tree T2 with n0 edges such that T2 decomposes Kn0,n0 . In the latter case, we can improve the bound if there exists a prime p such that d3m/2e p 2m 1.