Substructure, subgraph, and walk counts as measures of the complexity of graphs and molecules

In discussions of unsaturated compounds represented by multigraphs it is necessary to distinguish between the notions of substructure and subgraph. Here the difference is explained and exemplified, and a computer program is introduced which for the first time is able to construct and count all substructures and subgraphs for a colored multigraph (a molecular compound which may contain unsaturation and heteroatoms). Construction of all substructures and subgraphs is computationally demanding; therefore, two alternatives are pointed out for the treatment of large sets of compounds: (i) Often it will suffice to consider counts of substructures/subgraphs up to a certain number of edges only, information which is provided by the program much more rapidly. (ii) It is shown that information equivalent to that gained from substructure or subgraph counts is often far more easily available using walk counts. Some problems and their consequences for substructure/subgraph/walk counts are discussed that arise from the models used in organic chemistry for certain compounds such as aromatics and from the necessity to express qualitative features of molecular structures numerically.