On 2-fold graceful labelings

Abstract

A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$ edges, it is conjectured that there exists a labeling $f:V(T)\to \{0,1,\dots ,n\}$ such that the set of induced edge labels $\{|f(u)–f(v)|:\{u,v\}\in E(T)\}$ is exactly $\{1,2,\dots ,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most 2. A 2-fold graceful labeling of a graph (or multigraph) $G$ with $n$ edges is a one-to-one function $f:V(G)\to \{0,1,\dots ,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\{1,2,\dots ,\lfloor n/2\rfloor \}$, and if $n$ is odd, one copy of $\{\lfloor n/2\rfloor \}$. When $n$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n\ne 1\mathrm{mod}4$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is 2-fold graceful.