THE GRAPH ISOMORPHISM-PROBLEM Academic Article uri icon

abstract

  • A chemically and graphtheoretically relevant problem is that of determining whether a pair of graphs G and G are isomorphic. A twostage computational test is developed. In the first stage an eigenvalueeigenprojector tabular graphtheoretic 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. Copyright 1991 John Wiley & Sons, Inc.

published proceedings

  • JOURNAL OF COMPUTATIONAL CHEMISTRY

author list (cited authors)

  • LIU, X., & KLEIN, D. J.

citation count

  • 30

complete list of authors

  • LIU, X||KLEIN, DJ

publication date

  • December 1991

publisher