Home | RNA Tutorials | RNA Structure | Graph Theory and RNA Structures | Spectral Graph Analysis | Clustering RNA Motifs |

......

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.