To access the full text documents, please follow this link: http://hdl.handle.net/2117/8171

Title:	Every tree is a large subtree of a tree that decomposes Kn or Kn,n
Author:	Lladó Sánchez, Ana M.; López Masip, Susana Clara; Moragas Vilarnau, Jordi
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	Let T be a tree with m edges. A well-known conjecture of Ringel states that T decomposes the complete graph $K_{2m+1}$. Graham and Häggkvist conjectured that T also decomposes the complete bipartite graph $K_{m,m}$. In this paper we show that there exists an integer n with n ≤[(3m - 1)/2] and a tree T₁ with n edges such that T₁ decomposes $K_{2n+1}$ and contains T. We also show that there exists an integer n' with n' ≥ 2m-1 and a tree T₂ with n' edges such that T₂ decomposes $K_{n',n'}$and contains T. In the latter case, we can improve the bound if there exists a prime p such that [3m/2] ≤ p < 2m - 1.
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph labelings -Graph theory -Grafs, Teoria de
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Published version Article
Share:

Show full item record