The graph isomorphism problem
- 1 December 1991
- journal article
- research article
- Published by Wiley in Journal of Computational Chemistry
- Vol. 12 (10) , 1243-1251
- https://doi.org/10.1002/jcc.540121012
Abstract
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.Keywords
This publication has 24 references indexed in Scilit:
- Highly Regular GraphsaAnnals of the New York Academy of Sciences, 1989
- On the Construction of Endospectral GraphsaAnnals of the New York Academy of Sciences, 1989
- Combinatorial models and algorithms in chemistry. Search for isomorphisms and automorphisms of molecular graphsJournal of Computational Chemistry, 1988
- Unique description of chemical structures based on hierarchically ordered extended connectivities (HOC procedures). I. Algorithms for finding graph orbits and canonical numbering of atomsJournal of Computational Chemistry, 1985
- On Randic's molecular identification numbersJournal of Chemical Information and Computer Sciences, 1985
- A technique for determining the symmetry properties of molecular graphsJournal of Computational Chemistry, 1983
- THE CONSTRUCTION OF COSPECTRAL COMPOSITE GRAPHSAnnals of the New York Academy of Sciences, 1979
- The graph isomorphism diseaseJournal of Graph Theory, 1977
- Drum Shapes and Isospectral GraphsJournal of Mathematical Physics, 1966
- On the Line Graph of a Symmetric Balanced Incomplete Block DesignTransactions of the American Mathematical Society, 1965