Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Asymptotically optimal tree-packings in regular graphs. | Asymptotically optimal tree-packings in regular graphs Alexander Kelmans Rutgers University New Brunswick New Jersey and University of Puerto Rico San Juan Puerto Rico kelmans@ Dhruv Mubayi t School of Mathematics Georgia Institute of Technology Atlanta GA 30332-0160 USA Microsoft Research One Microsoft Way Redmond WA 98052-6399 mubayi@ Benny Sudakov Ỉ Department of Mathematics Princeton University Princeton NJ 08544 USA and Institute for Advanced Study Princeton NJ 08540 USA bsudakov@ Submitted February 15 2001 Accepted November 21 2001. AMS Subject Classifications 05B40 05C05 05C35 05C70 05D15 Keywords Packing trees matchings in hypergraphs Abstract Let T be a tree with t vertices. Clearly an n vertex graph contains at most n t vertex disjoint trees isomorphic to T. In this paper we show that for every e 0 there exists a D e t 0 such that if d D e t and G is a simple d-regular graph on n vertices then G contains at least 1 e n t vertex disjoint trees isomorphic to T. 1 Introduction We consider simple undirected graphs. Given a graph G and a family F of graphs an F-packing of G is a subgraph of G each of whose components is isomorphic to a member of F. The F-packing problem is to find an F-packing of the maximum number of vertices. There are various results on the F-packing problem see . 3 9 10 11 12 13 14 15 . Research supported in part by the National Science Foundation under DIMACS grant CCR 91-19999. Research supported in part by the National Science Foundation under grant DMS-9970325. Research supported in part by NSF grants DMS-0106589 CCR-9987845 and by the State of New Jersey. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R38 1 When F consists of a single graph F we abuse notation by writing F-packing. The very special case of the F-packing problem when F K2 a single edge is simply that of hnding a maximum matching. This problem is well-studied and can be solved in polynomial time see for example 15 . .
