COMPUTER-GENERATION OF ACYCLIC GRAPHS BASED ON LOCAL VERTEX INVARIANTS AND TOPOLOGICAL INDEXES - DERIVED CANONICAL LABELING AND CODING OF TREES AND ALKANES

A new procedure (GENLOIS) is presented for generating trees or certain classes of trees such as 4-trees (graphs representing alkanes), identity trees, homeomorphical irreducible trees, rooted trees, trees labelled on a certain vertex (primary, secondary, tertiary, etc.). The present method differs from previous procedures by differentiating among the vertices of a given parent graph by means of local vertex invariants (LOVIs). New graphs are efficiently generated by adding points and/or edges only to nonequivalent vertices of the parent graph. Redundant generation of graphs is minimized and checked by means of highly discriminating, recently devised topological indices based either on LOVIs or on the information content of LOVIs. All trees on N + 1 (N + 1 < 17) points could thus be generated from the complete set of trees on N points. A unique cooperative labelling for trees results as a consequence of the generation scheme. This labelling can be translated into a code for which canonical rules were recently stated by A.T. Balaban. This coding appears to be one of the best procedures for encoding, retrieving or ordering the molecular structure of trees (or alkanes).