Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648721 | Discrete Mathematics | 2010 | 5 Pages |
Abstract
Let TT be a tree with mm edges. A well-known conjecture of Ringel states that TT decomposes the complete graph K2m+1K2m+1. Graham and Häggkvist conjectured that TT also decomposes the complete bipartite graph Km,mKm,m. In this paper we show that there exists an integer nn with n≤⌈(3m−1)/2⌉n≤⌈(3m−1)/2⌉ and a tree T1T1 with nn edges such that T1T1 decomposes K2n+1K2n+1 and contains TT. We also show that there exists an integer n′n′ with n′≥2m−1n′≥2m−1 and a tree T2T2 with n′n′ edges such that T2T2 decomposes Kn′,n′Kn′,n′ and contains TT. In the latter case, we can improve the bound if there exists a prime pp such that ⌈3m/2⌉≤p<2m−1⌈3m/2⌉≤p<2m−1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
A. Lladó, S.C. López, J. Moragas,