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) \rightarrow \{0, 1, \ldots, n\} \) such that the set of induced edge labels \( \{ |f(u) – f(v)| : \{u,v\} \in E(T) \} \) is exactly \( \{1, 2, \ldots, 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) \rightarrow \{0, 1, \ldots, n\} \) such that the multiset of induced edge labels is comprised of two copies of each element in \( \{1, 2, \ldots, \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 \neq 1 \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.