On k-graceful digraphs

Abstract

In this paper we extend the idea of k-graceful labeling of undirected graphs to a directed graphs: A simple directed graph D with n vertices and e edges is labeled by assigning each vertex a distinct element from the set ?c+k = {0,1,2.....e + k - 1}, where is a positive integer and an edge xy from vertex x to vertex y is labeled with ?(x, y) = ?(y) - ?(x)mod(e + k), where ?(y) and ?(x) are the values assigned to the vertices y and x respectively. A labeling is a k-graceful labeling if all ?(x, y) are distinct and belong to {k, k + 1,k + e-1}. If a digraph D admits a k-graceful labeling then D is a fc - graceful digraph. We also provide a list of values of fc for which the unidirectional cycle C?n admits a k-graceful labeling. Further, we give a necessary and sufficient condition for the outspoken unicyclic wheel to be k-graceful and prove that to provide a list of values of k > 1, for which the unicyclic wheel W?n is fc-graceful is NP - complete.