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.