Every Tree is a subtree of Graceful Tree, Graceful Graph and Alpha-labeled Graph

Abstract

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, \ldots, m\}\) such that when every edge \(uv\) is assigned the edge label \(|f(u) – f(v)|\), then the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph. A graceful labeling of a graph \(G\) with \(m\) edges is called an \(\alpha\)-labeling if there exists a number \(\alpha\) such that for any edge \(uv\), \(\min\{f(u), f(v)\} \leq \lambda < \max\{f(u), f(v)\}\). The characterization of graceful graphs appears to be a very difficult problem in Graph Theory. In this paper, we prove a basic structural property of graceful graphs, that every tree is a subtree of a graceful graph, an \(\alpha\)-labeled graph, and a graceful tree, and we discuss a related open problem towards settling the popular Graceful Tree Conjecture.