Further Results on Graceful Digraphs

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. In this paper, we prove a general result on graceful digraphs of which Du and Sun’s conjecture (J. Beijing Univ. Posts Telecommun, 17: 85–88 1994) is a special case. Further, we provide an upper bound for the number of non isomorphic graceful directed cycles obtained from a graceful labeling of the unicycle of the unicycle →Cn.