Semi-Complementary Graphs

S. V. Siva Rama Raju, I. H. Nagaraja Rao

Abstract

In communication networks, a secret message is being sent by means of adjacency matrix associated with a simple graph  G. As it is easily traceable instead of adjacency, non adjacency matrix (that is associated with the complementary graph  Gc) is being preferred. Now, we introduce another type of graph called as semi-complementary graph Gsc of G. This is a spanning subgraph of Gc and hence more secrecy can be achieved by using this in defence problems.Already semi complete graphs have been introduced ([1, 2]) and it is observed that for such graphs Gsc = Gc. Semi complete graphs are playing a vital role in sharing a secret code in parts, by two individuals, instead of one. Thus these are useful in bank transactions.