Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/8171

Every tree is a large subtree of a tree that decomposes Kn or Kn,n
Lladó Sánchez, Ana M.; López Masip, Susana Clara; Moragas Vilarnau, Jordi
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
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.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Graph labelings
Graph theory
Grafs, Teoria de
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
info:eu-repo/semantics/publishedVersion
Article
         

Mostra el registre complet del document

Documents relacionats

Altres documents del mateix autor/a

Lladó Sánchez, Ana M.; Moragas Vilarnau, Jordi
Lladó Sánchez, Ana M.; Moragas Vilarnau, Jordi
Hamidoune, Yahya ould; Lladó Sánchez, Ana M.; López Masip, Susana Clara
Hamidoune, Yahya ould; Lladó Sánchez, Ana M.; López Masip, Susana Clara
Drmota, Michael; Lladó Sánchez, Ana M.