Remarks on the placeability of isomorphic trees in a complete graph

✍ Scribed by Hasunuma, Toru; Shibata, Yukio

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 99 KB
• Volume: 21
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199601)21:1<41::aid-jgt5>3.0.co;2-m

✦ Synopsis

Let Tp be any tree of order p and A ( T p ) stand for the maximum degree of the vertices of Tp. We prove the following theorem. "If A(Tp) 5 pi, where p > 2i, then Tp is i-placeable in Kp" is true if and only if i = 1, 2, and 3. 0 1996 John Wiley & Sons, Inc.

Suppose G is a graph and V ( G ) , E ( G ) are the vertex set of G, the edge set of G, respectively. As usual A ( G ) stands for the maximum degree of the vertices of G. Let T,, be any tree of order p .

Suppose H is a graph of order p . Let pi be a permutation on V ( H ) for 1 5 i 5 n. Let

If the following condition is satisfied, then H is n-placeable in K,,.

We consider p1 as the identity permutation. Each pi is called a packing function of H. Then {cp 1, . . . , 9,) is called a system of packing functions of H .

For 2-placeability, H . J . Straight observed that any tree except for star is 2-placeable in a complete graph (see [l]). For 3-placeability of a tree in a complete graph, we independently proved in the following theorem equivalent to Wang and Sauer's result in [3].

Theorem 0 3]. If A(T,,) 5 p -3, where p > 6, then T p is 3-placeable in K,,.

From these results, the following proposition is true for i = 1, 2, and 3.