A graph theoretical basis for structural chemistry. I. Structures based on trivalent graphs with 10 vertices
Milan Randić · Acta Crystallographica Section A · 1978
This paper is the first in a series concerned with a particular graph theoretical scheme for enumeration and derivation of structures of prescribed form. The problem spoken to by this work is that of finding a unique formal procedure for generating all distinct (i.e. non-isomorphic) graphs of a given number of vertices and prescribed valency. Here the scheme is outlined as applied to a search for regular trivalent graphs, some of which correspond to trivalent polyhedra. A systematic procedure for obtaining the number of equivalence classes of the adjacency matrices associated with trivalent graphs of n points is described. The procedure is of general applicability, though no proof of its correctness is offered. Instead, a number of examples are discussed, and its application is illustrated. The scheme is based on consideration of unique matrices associated with graphs which in turn are determined so that the corresponding binary code obtained by reading the rows of the matrix from left to right and from top to bottom represents the smallest possible binary code. Part of the scheme consists in finding all acceptable matrices, testing them for isomorphism, and selecting those which satisfy additional restrictions and ensure that the derived graph represents a structure of interest.