Revisiting Graceful Labelings of Graphs

Abstract

For a graph $G$ of size $m$, a graceful labeling of $G$ is an injective function $f:V(G)\to \{0,1,\dots ,m\}$ that gives rise to a bijective function $f^{\prime }:E(G)\to \{1,2,\dots ,m\}$ defined by $f^{\prime }(uv)=|f(u)–f(v)|$. A graph $G$ is graceful if $G$ has a graceful labeling. Over the years, a number of variations of graceful labelings have been introduced, some of which have been described in terms of colorings. We look at several of these, with special emphasis on some of those introduced more recently.