TY - JOUR

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

AU - Rücker, Gerta

AU - Rücker, Christoph

PY - 2001/11/1

Y1 - 2001/11/1

N2 - 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.

AB - 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.

KW - Chemistry

UR - https://www.mendeley.com/catalogue/602c92a3-e2eb-3433-be84-95045130c492/

UR - http://www.scopus.com/inward/record.url?scp=0035526172&partnerID=8YFLogxK

U2 - 10.1021/ci0100548

DO - 10.1021/ci0100548

M3 - Journal articles

VL - 41

SP - 1457

EP - 1462

JO - Journal of Chemical Information and Computer Sciences

JF - Journal of Chemical Information and Computer Sciences

SN - 0095-2338

IS - 6

ER -