Packing Four Copies Of A Tree Into A Complete Bipartite Graph

For any graph G, we use V(G) and E(G) to denote the vertex set and the edge set of G respectively. An acyclic graph is one that contains no cycles. A connected acyclic graph is called a tree and acyclic graphs are usually called forest. We use Bn or Kt,n-t to represent a complete bipartite graph of order n with bipartition of (X, Y) such that|X| =n and |Y| =n- t. Note that up to isomorphism, Bn is not uniquely defined for n ?4 and t ? 1. By an embedding ? of a bipartite graph G in Bn, we mean that ? is an injection from V(G) into V(Bn) such that ?(V0)(?) X0 and ?(V1)(?)C X1 where (V0, V1)and (X0,X1) are the given bipartitions of G and Bn, respectively. Let G' be a subgraph of the graph G. If there are k embeddings ?i(1?i?k) of G in Bn such that ?i(G) and?j(G) are edge-disjoint for all i ? j, then we say that there is a k-packing of G in Bn and(?1,…,?k) is the k-packing of G in Bn.Wang gives a conjecture[7]: for each tree T of order n and each integer k > 2,there is a k-packing of T in some complete bipartite graph Bn+k-1 whose order is n + k - 1.Paper[5] proved the conjecture is right when k = 2 and paper[7] showed the conjecture is right when k = 3. This paper showed the conjecture is right when k = 4. This paper consists of three parts.In the first chapter, A survey of k-packing of tree T in Bn is given.In the second chapter, we get some main lemmas about there is a 4-packing of T in a complete bipartite graph Bn+3.In the third chapter, we give the proof of main theorem: There is a 4-packing of T in a complete bipartite graph Bn+3.