Exploring the Limits of Graph Invariant- and Spectrum-Based Discrimination of (Sub)structures

INTRODUCTION Substructures and subgraphs of chemical structures are becoming increasingly important in description of chemical compounds' properties and reactivity, in similarity and complexity considerations, 1b,c in physical and biological property prediction, 1d and in automatic structure elucidation from spectral data. 2 We recently developed computer programs capable of finding all connected subgraphs in simple graphs, 3 all connected substructures and distinct connected substructures in colored multigraphs and chemical structures, and all connected substructures and subgraphs and distinct connected substructures and subgraphs in colored multigraphs and chemical structures. 5 In such an endeavor the ability to distinguish very similar graphs is obviously a central issue and is in fact the limiting factor. Since a fast computer method for reliably discriminating all nonisomorphic graphs was not at our hands, the best we could do was to use graph invariants of disc