Construction of graceful digraphs using algebraic structures

摘要

In the early 1980's Bloom and Hsu extended the notation of graceful labelings to directed graphs, and gave a relationship between graceful digraphs and a variety of algebraic structures. In this paper using a cyclic (v, k, λ) difference set with λ copies of elements of Z_v {0}, we construct graceful digraphs of k vertices and v- 1 arcs. It is known that if gracefully labelled graph has e edges then its symmetric digraph is graceful with the same vertex labels. Although, the cycle C_m is not graceful for m = 1,2 (mod 4) we show that the symmetric digraph based on cycle C_m i.e the double cycle, DC_m which is constructed from a m-cycle by replacing each edge by a pair of arcs, edge xy gives rise to arcs (x, y) and (y, x), is graceful for any m vertices specifically for m ≡ 1,2 (mod 4).