The inventive use of concepts from Graph Theory plays a significant role in hiding the original Plain-text for resulting in a significantly safe data transfer. In this work, the tree traversal algorithms like Inorder, Preorder, Postorder, Kruskal’s algorithm for making minimal spanning tree and the modified graph labelling scheme of graceful labelling allowing repetition of exactly one vertex label for certain graphs, have been employed to create highly hidden Cipher-texts. Encryption and decryption algorithms for all these methods are being presented in this work.