Graph Isomorphism

Biologically-related RNA molecules tend to have similar secondary structures. Thus, comparing RNA graphs can help identify RNA molecules that are structurally, functionally and evolutionarily related. The problem of deciding algorithmically whether two graphs are isomorphic or structurally equivalent is known as the graph isomorpism problem. Many heuristic methods exist to determine structurally equivalent graphs, but the general solution to the problem has, so far, eluded mathematicians.

We use Laplacian eigenvalue spectra to compare and find structurally similar graphs (see RNA Matrix program). Two graphs are deemed to be isomorphic when they have the same eigenvalue spectrum. This method is imperfect since cospectral non-isomorphic graphs exist. For Laplacian spectra, the method fails less than 10 to 15 percent of the cases.

......

Mathematical results related to graph isomorphism

Definition:

Two graphs are said to be isomorphic when they are structurally equivalent irrespective of the vertex labels.

Theorem:

Isomorpic graphs have identical eigenvalues.

Proof:

Isomorphic graphs are related by permutation of vertex labels. Label-permutation of matrices is a linear transformation. Thus, isomorphic graphs are represented by similar matrices according to the following theorem.

Theorem: Two square matrices are similar if and only if they represent the same linear transformation.

Similar matrices are isomorphic since

Theorem: Similar matrices have the same characteristic polynomial and therefore the same eigenvalues.

However, non-isomophic graphs can also have identical eigenvalues. These are called co-spectral non-isomophic graphs.