A NOVEL DUAL-LAYER GRAPH ENCRYPTION SCHEME USING TOTAL COLORING AND MATRIX-BASED ENCODING

This study introduced a graph-based encryption framework grounded in the concept of total coloring of path graphs. By combining graph-theoretic representation with matrix-based transformations, the proposed method establishes a dual-layer encoding mechanism in which both vertices and edges contribute to the encrypted structure. This integrated approach enhances the structural complexity of the ciphertext when compared with conventional graph labeling techniques that typically rely on a single layer of encoding. From a computational perspective, the scheme remains efficient for practical implementation, particularly in environments where structured data representation is advantageous. The use of total coloring imposes stricter assignment constraints, which in turn strengthens the encoding process by increasing interdependencies among graph components. In addition, the reliance on a symmetric key model ensures operational simplicity, although the overall security of the system is closely tied to the appropriate selection and management of the key matrix. The framework also offers flexibility for implementation using widely adopted programming platforms such as C++, Java, and Python, supporting its applicability in real-world scenarios. At the same time, the current model presents opportunities for further refinement. For instance, extending the approach to more complex graph classes, including cyclic, tree-based, and hybrid structures, may provide additional layers of security and structural diversity. Another direction for improvement lies in optimizing the size of the generated ciphertext matrix. Reducing storage requirements and transmission overhead would enhance the practicality of the method, particularly for large-scale data applications. Segment-based encryption strategies, where longer messages are divided and processed independently, may offer a feasible solution in this regard. Future investigations could also consider integrating the proposed framework with public key cryptographic models to strengthen security guarantees and broaden its applicability. Additionally, optimizing matrix operations through advanced algorithms, as well as exploring parallel or distributed computing techniques, may significantly improve performance when handling large datasets. In summary, the results of this work indicate that total coloring provides a promising foundation for the development of graph-based cryptographic systems. The proposed scheme demonstrates that incorporating structural and combinatorial properties of graphs can lead to encryption mechanisms that are both flexible and robust, making them suitable for evolving communication requirements.

1.                Amudha, P., Jayapriya, J., & Gowri, J. (2021). An algorithmic approach for encryption using graph labeling. Journal of Physics: Conference Series, 1770. 2.                Gallian, J. A. (2015). A dynamic survey of graph labeling. Electronic Journal of Combinatorics. 3.                Hill, L. S. (1929). Cryptography in an Algebraic Alphabet, American Mathematical Monthly, 36(6), 306–312. 4.                Kahate, A. (2011). Cryptography and network security. 5.                MacDougall, J. A., Miller, M., Slamin, & Wallis, W. D. (2002). Total labeling of graphs. 6.                Shanmugam, A., & Durairaj, M. (2018), Graph Theory Based Encryption Techniques for Secure Communication, International Journal of Pure and Applied Mathematics, 119(15), 2345–2354. 7.                Singh, S., & Sharma, V. (2020), Applications of Graph Labeling in Cryptography, Journal of Discrete Mathematical Sciences and Cryptography, 23(4), 925–938. 8.                Schneier, B. (1996), Applied Cryptography (2nd ed.). Wiley. 9.                West, D. B. (2001). Introduction to graph theory.