Embedding an Arbitrary Tree in a Graceful Tree

作者：Sethuraman G^*; Ragukumar P; Slater Peter J

来源：Bulletin of the Malaysian Mathematical Sciences Society, 2016, 39(S1): S341-S360.

DOI：10.1007/s40840-015-0210-5

• Graceful tree
• Graceful Tree Conjecture
• Graceful Tree Embedding
• Graceful labeling
• Graph labeling

A function f is called a graceful labeling of a graph G with m edges if f is an injective function from V(G) to {0, 1, 2,..., m} such that when every edge uv is assigned the edge label vertical bar f (u) - f (v)vertical bar, then the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph. The popular Graceful Tree Conjecture states that every tree is graceful. The Graceful Tree Conjecture remains open for over four decades. Although there are a few general results and techniques on the construction of graceful trees, settling the conjecture seems to be very hard. In this paper, we have introduced a new and different method of constructing graceful trees from a given arbitrary tree. More precisely, we show that every tree can be embedded in a graceful tree with at most km edges, k < [m/4], where m is the number of edges of the given arbitrary tree. Further, we pose a related open problem toward settling the Graceful Tree Conjecture.

• 出版日期2016-6