On Graceful Unicyclic Wheels

Abstract

A digraph \(D\) with \(e\) edges is labeled by assigning a distinct integer value \(\theta(v)\) from \(\{0, 1, \ldots, e\}\) to each vertex \(v\). The vertex values, in turn, induce a value \(\theta(u,v) = \theta(v) – \theta(u) \mod (e + 1)\) on each edge \((u,v)\). If the edge values are all distinct and nonzero, then the labeling is called a \emph{graceful labeling} of a digraph. Bloom and Hsu conjectured in 1985 that “all unicyclic wheels are graceful.” In this paper, we prove this conjecture.