All trees are 1-embeddable and all except stars are 2-embeddable

✍ Scribed by C.R.J. Clapham; J. Sheehan

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 484 KB
• Volume: 120
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90585-h

✦ Synopsis

Clapham, C.R.J. and J. Sheehan, All trees are I-embeddable and all except stars are 2-embeddable, Discrete Mathematics 120 (1993) 253-259.

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism 4 of K, such that E(G)nE(&G))=@.

It is known that all trees Twith n (2 2) vertices and T$G K1.._ 1 are embeddable. We say that G is I-embeddable if, for every edge e, there is an automorphism 4 of K, such that E(G)nE(4(G))= {e}; and that it is 2-embeddable if, for every pair e,, ez of edges, there is an automorphism #J of K, such that E(G)nE(~(G))={ et, e2}, We prove here that all trees with n (2 3) vertices are 1-embeddable; and that all trees T with n (>4) vertices and T$ KI,._ 1 are 2embeddable.

In a certain sense, this result is sharp.