A Study on Labelings of Directed Graphs

Abstract

In this thesis, two types of graph labeling problems has been studied namely, graceful and sequential labeling problems of digraphs. The use of modular arithmetic in these labeling ties them to a variety of algebraic problems. Using some of the algebraic structures such as (v; k; λ) di erence set, complete mapping and partition theory the gracefulness of some known class of digraphs has been proved. A construction of bigraphs from digraphs (vice-versa) are given using an adjacency matrix. Using this constructive method it is proved that, the graceful labelings of some class of bigraphs gives rise to graceful digraphs and vice-versa. Further, a relationship between the sequential labelings and graceful labelings of digraphs has been given. With this relation it is proved that, the sequential digraphs are related to near complete mappings and cyclic multiplicative groups. Also, for some more class of digraphs its gracefulness and sequentialness has been proved.