Contact Us
Journal Statistics & Approval Details
Recent Published Paper
Our Author's Feedback
 •  SJIF Impact Factor: 8.067       •  ISRA Impact Factor 7.894       •  Hard Copy of Certificates to All Authors       •  DOI by Crossref for all Published Papers       •  Soft Copy of Certificates- Within 04 Hours       •  Authors helpline No: +91-8813907089(Whatsapp)       •  No Publication Fee for Paper Submission       •  Hard Copy of Certificates to all Authors       •  UGC Approved Journal: IJRASET- Click here to Check       •  Conference on 18th and 19th Dec at Sridevi Womens Engineering College     
ISSN: 2321-9653
Estd : 2013

Ijraset Journal For Research in Applied Science and Engineering Technology

A Graph-Theory Based Encryption Model Utilizing Spanning Tree Transformations

Authors: Vidhya S, Sivashankari R

DOI Link: https://doi.org/10.22214/ijraset.2026.79150

Certificate: View Certificate

Abstract

We will examine how the messages can be encrypted and decrypted using the complete graph and spanning tree principles from graph theory.

Introduction

The paper explores the use of graph theory, specifically spanning trees, in cryptography to secure digital communication. Spanning trees, which connect all vertices of a graph without cycles, provide an organized and efficient structure for encoding messages. In the proposed method, each character of a message is represented as a graph vertex, edges are weighted based on an encoding table, and a minimal spanning tree is constructed to determine the path for encrypting the message. This approach allows systematic transformation of the original text into an encrypted form, which can later be decrypted using the same spanning tree structure. The technique offers structural clarity, reduced complexity, and flexible encoding, demonstrating the potential of integrating graph theory with cryptography for secure information transmission.

Conclusion

In this paper, we have studied to encrypt the original plain text into numerical values by using spanning tree concept, for this first we convert the letter in plain text into vertices and join all the vertices to form cycle graph, then by using encoding table we find the value for edges so that we get weighted graph. We add extra edges for the weighted graph to form complete weighted graph. By using Kruskal’s or prim’s algorithm we can construct minimal spanning tree then convert into matrix form. In encryption process, we use public key as matrix form (upper triangular matrix) to get cipher text. In decryption process, we use inverse of public key as matrix form to decrypt the cipher text and we get the original plain text.

References

[1] Corman TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithm 2nd edition, McGraw-Hill. [2] Etaiwi W. M. A., Encryption Algorithm using Graph Theory. Journal of Scientific Research and Reports. 3(19) (2014) 2519-2527. [3] Janaki, G., & Vidhya, S. (2016). On the integer solutions of the Pell equation t y x 4 20 2 2-=. International Journal of Multidisciplinary Research and Development, 3(5), 39-42. [4] Janaki, G., & Vidhya, S. (2016). On the integer solutions of the Pell equation k y x 9 79 2 2=-. International Journal of Scientific Research in Science, Engineering and Technology, 2(2), 1195-1197. [5] Janaki, G., & Vidhya, S. (2016). On the negative Pell equation 3 21 2 2-= x y. International Journal of Applied Research, 2(11), 462-466. [6] Krishnaa A., Certain specific graphs in cryptography, Advances and Applications in Discrete Mathematics, 26(2) (2021) 157-177. [7] Krishnaa A. and Dulawat M. S., Algorithms for Inner Magic and Inner Antimagic Labelings for Some Planar Graphs, Informatica (Lithuania), 17(3) 2006 393-406. [8] Litta, E., & Dharshini, S. M. (2023). Proper Colourings in r-Regular Modified Zagreb Index Graph. International Journal for Research in Applied Science & Engineering Technology (IJRASET), 11(3), 1553-1558. [9] Litta, E., & Datchini, S. (2023). Proper Colourings in r–Regular Zagreb Index Graph. Aryabhatta Journal of Mathematics and Informatics, 15(1), 149-154. [10] E Litta, S Narmadha. Proper Colourings in -Regular Inverse Sum Indeg Index Graphs. Research and Applications Towards Mathematics and Computer Science Vol. 9, BP International, pp.66-76, 2024. ?hal-05249331?. [11] Uma Dixit, CRYPTOGRAPHY A GRAPH THEORY APPROACH, International Journal of Advance Research in Science and Engineering, 6(01) , 2017, BVCNSCS 2017. [12] Wael Mahmoud Al Etaiwi, Encryption Algorithm Using Graph Theory, Journal of Scientific Research and Reports, 3(19), 2519-2527, 2014, Article no. JSRR.2014.19.004. [13] Yamuna M, Meenal Gogia, Ashish Sikka, Md. Jazib Hayat khan. Encryption using graph theory and linear algebra. International Journal of Computer Application. ISSN:2250-1797, 2012.

Download Paper

Paper Id : IJRASET79150

Publish Date : 2026-03-31

ISSN : 2321-9653

Publisher Name : IJRASET

DOI Link : Click Here

Whatsapp Submit Paper Online