Packing three trees

✍ Scribed by Mariusz Woźniak

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 447 KB
• Volume: 150
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00204-a

✦ Synopsis

We present some results concerning edge-disjoint placement of two or three copies of a tree, as well as a theorem about the packing of three trees into the complete graph K,.

1. Terminology

We shall use standard graph theory notation. A finite, undirected graph G consists of a vertex set V(G) and edge set E(G). All graphs will be assumed to have neither loops nor multiple edges. For graphs G and H we denote by G U H the vertex disjoint union of graphs G and H and kG stands for vertex disjoint union of k copies of G. Suppose G1 ..... Gk are graphs of order n. We say that there is a packin9 of G1 ..... Gk (into the complete graph Kn) if there exist injections ~i" V(Gi) ~ V(Kn), i = 1 ..... k, such that ~*(E(Gi) n ~(E(Gj)) = 0 for i -¢ j, where the map ~* :E(Gi) ~ E(Kn) is the one induced by ~i.

A packing of k copies of a graph G will be called a k-placement of G. A packing of two copies of G (i.e. a 2-placement) is an embeddin9 of G (in its complement G). So, an embedding of a graph G is a permutation a on V(G) such that if an edge xy belongs to E(G) then a(x)a(y) does not belong to E(G). If there exists an embedding of G we say that G is embeddable.

The main references of the paper and of other packing problems are the last chapter of Bollob~s's book [1], the 4th chapter of Yap's book [12] and the survey paper [13], (cf. also [5,10]).

We shall need some additional definitions in order to formulate the results. Recall that Sn denote the star on n vertices. Let S~ be the graph obtained by subdividing one of the edges of S,-1. By analogy, denote by S~' the tree obtained by replacing one of the edges of S,_2 by the path of length 3.