Molecular graph enumeration

A.T. Balaban, ed.. Chemical Applications of Graph Theory, Academic Press, London, 1976. V. Kvasnicka and J. Pospichal, An improved version of the constructive enumeration of molecular graphs with described sequence of valence states. Chemom. Intell. Lab. Systems, 18 (1993) 171-181. 

From the point of view of the organic chemist, the relations between (which measures the thermodynamic stability of the molecule), X (which measures the energy of the first excited state relative to the ground state), N, M and K are of primary interest. Their importance stems from the fact that N, M and K can be quickly enumerated from the molecular graph. This makes a pencil and paper estimations of electronic properties of organic molecules possible. 

V. Kvasnicka, J. Pospichal, Canonical Indexing and Constructive Enumeration of Molecular Graphs, J.Chem.Inf.Comput.Sci., 30 (1990) 99-105. 

A restricted random walk matrix RRW was also proposed [Randic, 1995c] as an AxA dimensional square unsymmetric matrix that enumerates restricted (i.e. selected) random walks over a molecular graph (7. The i-j entry of the matrix is the probability of a random walk starting at vertex v, and ending at vertex v,- of length equal to the topological distance dij between the considered vertices ... 

However, a unique enumeration does not solve the problem of substructure search. Superimposition of substructures on structures would require the mapping of any combination of molecular graphs to find a graph isomorphism this is a tedious and time-consuming process. Because the rate of search is always one of the most important limitations for database applications, substructure search should incorporate additional preprocessing steps that restrict the number of molecules to be compared in an atom-by-atom matching algorithm. 

Kvasnicka, V. and Pospichal, J. (1990) Canonical indexing and constructive enumeration of molecular graphs. J. Chem. Inf. Comput. ScL,... 

Ordering implies a comparison, and instead of actual structures, one normally compares sequences of numbers characterizing a molecular graph of a chemical structure. Frequently the required sequences are derived from an enumeration of selected graph invariants. If the selected invariants lead to integers, then the ordering theory of Muirhead (1903) is most suited for these special cases ... 

By general structural isomer enumeration, we mean the enmneration of all molecular graphs corresponding to a molecular formula. We do not include here solutions that construct molecular structures from additional constraints, such as the presence or the absence of substructural fragments. Enmneration with constraints is reviewed in the next subsection. 

As a concrete example, linear recursions have been extensively developed for the case of enumerating Kekule structures. A (molecular) graph might be denoted G, and a subgraph identified as a Kekule structure k if it has the same number of vertices every one of which has exactly one incident edge in k. For instance, for naphthalene (Figure 1) one finds three Kekule structures each in correspondence... 

Speed plays an important role in structure enumeration, but only few theoretical results about the computational complexity are known. Goldberg s work [91] proves that the results in orderly enumeration can be computed with polynomial delay, and a paper of Luks [188] shows that isomorphism testing of molecular graphs can be done in polynomial time. 

One can enumerate other examples where the molecular graphs inform of the kinds and of the nature of interactions. The complexes of molecular hydrogen may be mentioned here. The dihydrogen possesses Lewis acid and Lewis base characteristics since the positive electrostatic potential is observed at the H-atoms, at edges... 

The computation of the characteri.stic polynomial for a molecular graph is a difficult numerical problem, and a wide range of methods have been developed for the efficient and accurate determination of its coefficients subgraph enumeration methods, recurrence relationships, graph decomposition, and linear algebra numerical methods. 

---