1. Substructure, Subgraph, and Walk Counts as Measures of the Complexity of Graphs and Molecules
- Author
-
Gerta Rücker and Christoph Rücker
- Subjects
Discrete mathematics ,Combinatorics ,Chemistry ,Computational Theory and Mathematics ,Multigraph ,Substructure ,General Chemistry ,Computer Science Applications ,Information Systems ,Mathematics - Abstract
In discussions of unsaturated compounds represented by multigraphs it is necessary to distinguish betweenthe notions of substructure and subgraph. Here the difference is explained and exemplified, and a computerprogram is introduced which for the first time is able to construct and count all substructures and subgraphsfor a colored multigraph (a molecular compound which may contain unsaturation and heteroatoms).Construction of all substructures and subgraphs is computationally demanding; therefore, two alternativesare pointed out for the treatment of large sets of compounds: (i) Often it will suffice to consider counts ofsubstructures/subgraphs up to a certain number of edges only, information which is provided by the programmuch more rapidly. (ii) It is shown that information equivalent to that gained from substructure or subgraphcounts is often far more easily available using walk counts. Some problems and their consequences forsubstructure/subgraph/walk counts are discussed that arise from the models used in organic chemistry forcertain compounds such as aromatics and from the necessity to express qualitative features of molecularstructures numerically. more...
- Published
- 2001
- Full Text
- View/download PDF