Two Conjectures on Graceful Digraphs

Abstract

A digraph D with p vertices and q arcs is labeled by assigning a distinct integer value g(v) from {0,1,...,q} to each vertex v. The vertex values, in turn, induce a value g(u, v) on each arc (u, v) where g(u, v) = (g(v)- g(u))(mod q + 1). If the arc values are all distinct then the labeling is called a graceful labeling of a digraph. Bloom and Hsu (SIAM J Alg Discr Methods 6:519-536, 1985) conjectured that, all unicyclic wheels are graceful. Also, Zhao et al. (J Prime Res Math 4:118-126, 2008) conjectured that, for any positive even n and any integer m ? 14, the digraph n-{long rightwards arrow}C<inf>m</inf>} is graceful. In this paper, we prove both the conjectures. © 2012 Springer.