The graph isomorphism problem

✍ Scribed by X. Liu; D. J. Klein

• Publisher: John Wiley and Sons
• Year: 1991
• Tongue: English
• Weight: 598 KB
• Volume: 12
• Category: Article
• ISSN: 0192-8651
• DOI: 10.1002/jcc.540121012

✦ Synopsis

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.