On the recognition of identical graphs representing molecular topology

Abstract

A procedure that can establish the identity of apparently different graphs is given. When certain instructions are followed, any adjacency matrix can be brought by permutations of rows and columns to a prescribed standard form, which is defined by a unique numbering of vertices. Identity of two graphs may then be established by a direct comparison of the transformed adjacency matrices. This approach is simple and practical. Furthermore, the associated unique numbering of atoms in a molecule may in itself be of significance for chemical nomenclature. Several molecular graphs describing polycyclic hydrocarbons illustrate the numbering procedure. The systematic generation of all structures having any prescribed number of vertices and edges is possible by adopting the present scheme of numbering of graphs. This is illustrated for systems having four and five vertices (atoms).