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.