Spectral Solution for Detecting Isomorphic Graphs with Nondegenerate Eigenvalues

Graph Isomorphism (GI) is to find a bijection between the vertices of two graphs G₁ and G₂, such that any two vertices in G₁ are adjacent if they are adjacent in G₂. There are several application areas in which graph isomorphism is required, such as study of organic compounds isomers, algorithms´ similarity analysis in profiling of Embedded Systems, VLSI circuits equivalence etc. The complexity of Graph Isomorphism problem is thought neither to be in P nor in NP-Complete although this has not been proved yet [1], [2]. We classify the graph on the basis of their Adjacency Matrix (AM) eigenvalues. A Non- degenerate eigenvalue corresponds to a distinct eigenvector instead of a subspace as in the case of degeneracy, making the problem simpler. We employ spectral decomposition of AM for finding a solution. Furthermore, we redefine the isomorphic transform equation by including eigenvectors into it. Index