Construction of Graceful Directed Graphs

By : Kumudakshi, S.M. Hegde

Page No: 253-264

Abstract
Dulmage and Mendelsohn while working on matrix reducibility observed that, there is a one-to-one correspondence between bigraphs and digraphs using the concept of adjacency matrices. In this paper we construct a relation between bigraphs and digraphs in terms of labelings. It is known that a graceful graph always gives rise to a graceful digraph. Start with any gracefully labeled undirected graph G with vertex labeling ?(x) for vertex x. Simply orienting the edges of G to point towards the larger vertex value produces a graceful digraph D with G as its underlying graph. Using the construction of bigraphs and digraphs, we show that the gracefulness of some classes of digraphs also gives rise to the gracefulness of its associated bigraph and vice versa.

Authors :
S.M. Hegde : Department of Mathematical and Computational Sciences National Institute of Technology, Karnataka, Surathkal Srinivasnagar - 575 025 Mangalore, India
Kumudakshi : Department of Mathematics, NMAM Institute of Technology, Nitte - 574110. Udupi Dist. Karnataka, India