Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-22T06:23:44.676Z Has data issue: false hasContentIssue false

Packing Trees into the Complete Graph

Published online by Cambridge University Press:  10 July 2002

EDWARD DOBSON
Affiliation:
Department of Mathematics and Statistics, PO Drawer MA, Mississippi State University, Mississippi State, MS 39762, USA (e-mail: [email protected])

Abstract

Let c [les ] 0.076122 and T1, T2,…, Tn be a sequence of trees such that [mid ]V(Ti)[mid ] [les ] ic(i−1). We prove that, if for each 1 [les ] i [les ] n there exists a vertex xiV(Ti) such that Tixi has at least (1−2c)(i−1) isolated vertices, then T1,…, Tn can be packed into Kn. We also prove that if T is a tree of order n+1−cn, c′ [les ] 1/25 (37−8 √21 ) ≈ 0.0135748, such that there exists a vertex xV(T) and Tx has at least n(1−2c′) isolated vertices, then 2n+1 copies of T may be packed into K2n+1.

Type
Research Article
Copyright
2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)