Any Tree with m edges can be embedded in a Graceful Tree with less than 4m edges and in a graceful planar graph

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

来源：Discrete Mathematics, 2017, 340(2): 96-106.

DOI：10.1016/j.disc.2016.07.009

• Graceful Tree
• Graceful Tree Conjecture
• Range-relaxed graceful labeling

A function f is called a graceful labeling of a graph G with in 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. In this paper, we prove a basic structural property of graceful graphs, that every tree can be embedded as a spanning subtree in a graceful planar graph. Also we show that any tree with m edges can be embedded in a graceful tree with less than 4m edges. A range-relaxed graceful labeling f is defined from V(G) to 0, 1, 2,..., m', where m' >= m. We improve the bound 2m-diam(T) on the range-relaxed graceful labeling given by Van Bussel (2002) for a tree T.

• 出版日期2017-2-6