Graceful digraphs and their applications
by
S.M. Hegde
Department of Mathematical and Computational Sciences, National Institute of Technology Karnataka,Surathkal, Srinivasnagar-575025. INDIA.

A directed graph D with n nodes ands e arcs, no self-loops and multiple edges is labeled by assigning to each node a distinct element from the set Z_e+1 = 0, 1, 2, …, e. An arc (x, y) from node x to y is labeled with l(xy)=(l(x)- l (y))(mod(e+1)), where l(x) and l(y) are the values assigned to the nodes x and y. A labeling is a *graceful labeling* of D if all l(xy) are distinct. Then D is called a *graceful digraph*.

The extension of graceful labelings to directed graphs arose in the characterization of finite neofields by Hsu and Keedwell .The relationship between graceful digraphs and a variety of algebraic structures including cyclic difference sets, sequenceable groups, generalized complete mappings, near complete mappings etc, are discussed.

Date received: August 17, 2004