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,\dots ,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)\}\le \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.