Further Results 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))(modq+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 C <inf>n</inf> ?. © 2015, Springer India Pvt. Ltd.