null
(Ed.)
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\colon V(T) \to \{0,1,\ldots,n\}$
such that the set of induced edge labels $\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$ is exactly $\{1,2,\ldots,n\}$.
We extend this concept to allow for multigraphs with edge multiplicity at most~$2$.
A \emph{2-fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is
a one-to-one function $f\colon V(G) \to \{0,1,\ldots,n\}$ such that
the multiset of induced edge labels is comprised of two copies of each element in $\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$ and, if $n$ is odd, one copy of $\bigl\{ \lceil n/2 \rceil \bigr\}$.
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 \not\equiv 1 \pmod{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.
more »
« less
