Premium
The graph isomorphism problem
Author(s) -
Liu X.,
Klein D. J.
Publication year - 1991
Publication title -
journal of computational chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.907
H-Index - 188
eISSN - 1096-987X
pISSN - 0192-8651
DOI - 10.1002/jcc.540121012
Subject(s) - graph isomorphism , combinatorics , adjacency matrix , adjacency list , eigenvalues and eigenvectors , isomorphism (crystallography) , mathematics , graph , invariant (physics) , discrete mathematics , line graph , chemistry , physics , quantum mechanics , crystal structure , mathematical physics , crystallography
A chemically and graph‐theoretically relevant problem is that of determining whether a pair of graphs G and G ′ are isomorphic. A two‐stage computational test is developed. In the first stage an “eigenvalue‐eigenprojector” tabular graph‐theoretic invariant is computed, whence if the two tables differ, G and G ′ must be nonisomorphic. The second stage, utilizing the tables of the first stage, orders the vertices, thereby leading to a special labeling for them, whence if the associated adjacency matrices for G and G ′ are equal, it must be that G and G ′ are isomorphic. The computational implementation, and testing of the algorithm is described.