Multifaceted Coding of Messages Using the Concepts of Graph Theory

The modern world has brought everyone closer through digital communications. People are highly dependent on digital services. The quest for a more complex coding algorithm to prevent data from breaching is never-ending. The more intricate the algorithm is, the safer the communication will be. So, the vogue is to find the most convoluted algorithm to provide secure communication. In this paper, a unique algorithm is developed using graph labeling, a complement of a graph and generalized complement. The algorithm generates two labeled graphs satisfying vertex even mean and vertex odd mean labelings. Encryption involves the process of complementation and combining both graphs by k-complementation of graphs to obtain a cipher graph. The reverse process is applied for decryption which involves splitting the cipher graph into two subgraphs by applying k-complement for the specified partition of the vertex set, taking the complement of the obtained graph/s and getting the values of the plaintext using the graph labeling method. The proposed algorithm is designed in such a way that it should be useful for all kinds of plaintexts even with special characters. To illustrate this, an app is developed in the Android platform for communication of messages using end-to-end encryption.