A Novel Dual-Layer Graph Encryption Scheme Using Total Colouring and Matrix-Based Encoding

The increasing reliance on digital communication systems necessitates the development of secure and efficient encryption techniques. In this paper, a graph-theoretic cryptographic framework based on total coloring of path graphs is introduced. The proposed method represents plaintext as a path graph, where both vertices and edges are assigned colors under total coloring constraints, resulting in a dual-layer encoding structure. This representation is transformed into a matrix form and encrypted using an invertible key matrix. Unlike traditional graph labeling approaches, the proposed scheme enhances structural complexity by incorporating both vertex and edge dependencies. The correctness of the method is theoretically justified, and its practical applicability is demonstrated through an illustrative example. Furthermore, the scheme exhibits linear computational complexity with respect to input size, making it suitable for efficient implementation. The approach provides improved resistance to structural and brute-force attacks due to its combinatorial encoding mechanism.