Proof of a conjecture on the gracefulness of a digraph

Abstract

A digraph D(V, E) is said to be graceful if there exists an injection f : V(G) → {0,1,... ,|E|}, such that the induced function f : E(G) → {1,2, ..., |E|) which is defined by f'(u, v) = [f(v) - f(u)] (mod |E| + 1) for every directed edge (u,v) is a bijection. Here, f is called a graceful labeling (graceful numbering) of D(V, E), and f is called the induced edge's graceful labeling of D. In this paper we discuss the gracefulness of the digraph n C _m and prove a conjecture that the digraph n C_m is a graceful digraph for any odd m and even n.