All trees are 1-embeddable and all except stars are 2-embeddable |
| |
Authors: | C R J Clapham and J Sheehan |
| |
Institution: | Department of Mathematical Sciences, University of Aberdeen, Aberdeen, UK |
| |
Abstract: | A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e1, e2 of edges, there is an automorphism φ of Kn such that E(G) ∩ E(φ(G))={e1, e2}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K1,n−1 are 2-embeddable. In a certain sense, this result is sharp. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|