Packing Trees into the Complete Graph

Abstract

Let c [les ] 0.076122 and T₁, T₂,…, T_n be a sequence of trees such that [mid ]V(T_i)[mid ] [les ] i−c(i−1). We prove that, if for each 1 [les ] i [les ] n there exists a vertex x_i ∈ V(T_i) such that T_i−x_i has at least (1−2c)(i−1) isolated vertices, then T₁,…, T_n can be packed into K_n. We also prove that if T is a tree of order n+1−c′n, c′ [les ] 1/25 (37−8 √21 ) ≈ 0.0135748, such that there exists a vertex x ∈ V(T) and T−x has at least n(1−2c′) isolated vertices, then 2n+1 copies of T may be packed into K_2n+1.