Graph theoretical procedures for determination of eigenspectra of molecular graphs: A brief review

Several graph theoretical procedures for obtaining eigenvalues of π-conjugated molecules have been discussed. Procedures for generation of characteristic polynomial corresponding to a molecular graph and its subsequent solutions for obtaining graph eigenspectra have been mentioned briefly. Moreover discussions on Laplacian and distance polynomials that offer more physico-chemical information already not present in the characteristic polynomial have also been carried out shortly.     

On eigenvalues and eigenvectors of graphs

It is known that there exists an equivalence relation between the adjacency matrix of graph theory and the Hückel matrix of Hückel molecular orbital theory. This paper presents some useful methods which allow us to systematically find eigenvalues and eigenvectors of various classes of graphs without calculating characteristic polynomials. Results obtained from this study give insight into the topological studies of molecular orbitals.Dedicated to Professor Frank Harary on the occasion of his 70th birthday.     

Generalized graphs and the Sinanoğlu graphical rules

A comparison of Sinano?lu's VIF (Ref. 1) and generalized graph is presented. Generalized graphs have vertex and edge weights. An abridged history of generalized graphs in theoretical chemistry is given. VIF 's are generalized graphs and therefore have adjacency matrices. The “graphical” rules of Sinano?lu can be represented by congruent transformations on the adjacency matrix. Thus the method of Sinano?lu is incorporated into the broad scheme of graph spectral theory. If the signature of a graph is defined as the collection of the number of positive, zero, and negative eigenvalues of the graph's adjacency matrix, then it is identical to the all-important {n₊, n₀, n_?}, the {number of positive, zero, and negative loops of a reduced graph} or the {number of bonding, nonbonding, and antibonding MO s}. A special case of the Sinano?lu rules is the “multiplication of a vertex” by (?1). In matrix language, this multiplication is an orthogonal transformation of the adjacency matrix. Thus, one can multiply any vertex of a generalized graph by ?1 without changing its eigenvalues.     

Symmetry factoring of the characteristic equations of graphs corresponding to polyhedra

A systematic procedure is described which uses two-and three-fold symmetry elements in graphs to reduce their adjacency matrices to lead to corresponding factorings of their characteristic polynomials. A graph splitting algorithm based on this matrix reduction procedure is described. Applications of these methods to the factoring of the characteristic polynomials of 28 polyhedra with nine or less vertices are given. General expressions for the eigenvalues of prisms, pyramids, and bipyramids in terms of the eigenvalues of their basal or equatorial regular polygons are calculated by closely related matrix methods.     

A representation of the McClelland method of graph splitting. Stack graphs

McClelland's rules on graph splitting can be represented using the generalized graph notation. Generalized graphs are edge- and vertex-weighted graphs, which are becoming important to chemical problems. By this the McClelland method of graph splitting has a wider range of applications. “Stack graphs” are constructed from identical “base graphs” by connecting corresponding vertices from one base to another. Their eigenvalues are related to the eigenvalues of the base graph. Two- and even three-layered graphs may be used as a simple model for the inter-ring interaction in a cyclophane.     

Spectral analysis of graphs by cyclic automorphism subgroups

The theory of spectral decomposition modulo subgroups of the graph automorphism group is extended to cyclic configurations of arbitrary rotational order. By regarding graphs with cyclic automorphisms as composite polymers of relatively simple monomeric structural units, it is shown that the spectrum of eigenvalues of many prominent molecular and nonmolecular families devolves to consideration of a single monomer-derived reduction network. As the only parameter associated with this network is the set of simple circuit eigenvalues, a direct connection is forged between the spectrum of a circuit and the spectrum of any cyclic array of the same periodicity.In addition to simplifying determination of individual graph spectra, the role of the automorphism reduction network in organizing and uniting disparate aspects of spectral theory is stressed. Systems sharing a subspectrum of identical eigenvalues are readily recognized from the graphic nature of networks. As previously, symbolic and notational devices are devised for greatest economy in the spectral analysis.Part 4 of the series Unified Theory of Graph Spectral Reduction Networks     

Graph theory and the PPP method

A graph theoretical formulation of the PPP method is presented. A weighted adjacency matrix of the PPP graph is given, wherein the off-diagonal elements are the bond orders. The automorphism group of the PPP graph is defined and shown to be isomorphic with the permutational subgroup of the permutation-inversion group of the molecule. It is demonstrated that the characteristic polynomial of the adjacency matrix of the PPP bond graph is invariant in every SCF iteration. It is shown that the PPP spectra discriminate isospectral graphs.Camille and Henry Dreyfus Teacher-Scholar.     

On the matching properties of three fence graphs

Supplementing the construction of a Möbius ladder graph derived from a ladder graph, the linear fence graph and cyclic fence graph are introduced. These have neater mathematical expressions for the perfect matching numbers and the matching and characteristic polynomials than the graphs in the previous families.     

Topological analysis of eigenvectors of the adjacency matrices in graph theory: The concept of internal connectivity

The topological properties of eigenvectors of adjacency matrices of a graph have been analyzed. Model systems studied are n-vertex-m-edge (n-V-m-E) graphs where n = 2–4, m = 1–6. The topological information contained in these eigenvectors is described using vertex-signed and edge-signed graphs. Relative ordering of net signs of edge-signed graphs is similar to that of eigenvalues of the adjacency matrix. This simple analysis has also been applied to naphthalene, anthracene and pyrene. It provides a sound basis for the application of graph theory to molecular orbital theory.     

Isospectral graphs and molecules

Isospectral molecules are nonidentical species whose molecular graphs have the same set of eigenvalues within HMO calculations. Several new concepts and methods for constructing pairs of isospectral graphs are discussed. Some possible experimental and theoretical applications of isospectral molecular pairs are outlined.     

On walks in molecular graphs.

Walks in molecular graphs and their counts for a long time have found applications in theoretical chemistry. These are based on the fact that the (i, j)-entry of the kth power of the adjacency matrix is equal to the number of walks starting at vertex i, ending at vertex j, and having length k. In recent papers (refs 13, 18, 19) the numbers of all walks of length k, called molecular walk counts, mwc(k), and their sum from k = 1 to k = n - 1, called total walk count, twc, were proposed as quantities suitable for QSPR studies and capable of measuring the complexity of organic molecules. We now establish a few general properties of mwc's and twc among which are the linear dependence between the mwc's and linear correlations between the mwc's and twc, the spectral decomposition of mwc's, and various connections between the walk counts and the eigenvalues and eigenvectors of the molecular graph. We also characterize the graphs possessing minimal and maximal walk counts.     

Energies of some Non-regular Graphs

The energy of a graph G is the sum of the absolute values of its eigenvalues. In this paper, we study the energies of some classes of non-regular graphs. Also the spectrum of some non-regular graphs and their complements are discussed.     

Graph theoretical procedure for obtaining analytical expressions of eigenspectra of linear chains and cycles with alternant vertex weights and same edge weight: Application to some complicated graphs

A graph theoretical procedure for obtaining eigenvalues of linear chains and cycles having alternant vertex weights (h₁, h₂, h₁, h₂, h₁, h₂, …) and the same edge weight (k) have been developed. The eigenvalues of some complicated graphs, such as graphs of linear polyacenes, methylene‐substituted linear polyacenes and cylindrical polyacene strips, stack graphs, and reciprocal graphs have been shown to be generated in closed analytical forms by this procedure. Many such graphs represent chemically important molecules or radicals. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

Quest for molecular graphs with maximal energy: a computer experiment

If lambda(1), lambda(2),..., lambda(n) are the eigenvalues of a graph G, then the energy of G is defined as E(G) = the absolute value of lambda(1) + the absolute value of lambda(2) +.... + the absolute value of lambda(n). If G is a molecular graph, representing a conjugated hydrocarbon, then E(G) is closely related to the respective total pi-electron energy. It is not known which molecular graph with n vertices has maximal energy. With the exception of m = n - 1 and m = n, it is not known which molecular graph with n vertices and m edges has maximal energy. To come closer to the solution of this problem, and continuing an earlier study (J. Chem. Inf. Comput. Sci. 1999, 39, 984-996, ref 7), we performed a Monte Carlo-type construction of molecular (n,m)-graphs, recording those with the largest (not necessarily maximal possible) energy. The results of our search indicate that for even n the maximal-energy molecular graphs might be those possessing as many as possible six-membered cycles; for odd n such graphs seem to prefer both six- and five-membered cycles.     

Degeneracy of some matrix graph invariants

New matrices associated with graphs and induced global and local topological indices of molecular graphs were proposed recently by Diudea, Minailiuc and Balaban. These matrices in canonical form are matrix graph invariants. A combined degeneracy of such invariants is considered. For every case of degeneracy corresponding graphs are presented.     

Novel shape descriptors for molecular graphs.

We report on novel graph theoretical indices which are sensitive to the shapes of molecular graphs. In contrast to the Kier's kappa shape indices which were based on a comparison of a molecular graph with graphs representing the extreme shapes, the linear graph and the "star" graph, the new shape indices are obtained by considering for all atoms the number of paths and the number of walks within a graph and then making the quotients of the number of paths and the number of walks the same length. The new shape indices show much higher discrimination among isomers when compared to the kappa shape indices. We report the new shape indices for smaller alkanes and several cyclic structures and illustrate their use in structure-property correlations. The new indices offer regressions of high quality for diverse physicochemical properties of octanes. They also have lead to a novel classification of physicochemical properties of alkanes.     

DAMQT 2.1.0: A new version of the DAMQT package enabled with the topographical analysis of electron density and electrostatic potential in molecules

DAMQT‐2.1.0 is a new version of DAMQT package which includes topographical analysis of molecular electron density (MED) and molecular electrostatic potential (MESP), such as mapping of critical points (CPs), creating molecular graphs, and atomic basins. Mapping of CPs is assisted with algorithmic determination of Euler characteristic in order to provide a necessary condition for locating all possible CPs. Apart from the mapping of CPs and determination of molecular graphs, the construction of MESP‐based atomic basin is a new and exclusive feature introduced in DAMQT‐2.1.0. The GUI in DAMQT provides a user‐friendly interface to run the code and visualize the final outputs. MPI libraries have been implemented for all the tasks to develop the parallel version of the software. Almost linear scaling of computational time is achieved with the increasing number of processors while performing various aspects of topography. A brief discussion of molecular graph and atomic basin is provided in the current article highlighting their chemical importance. Appropriate example sets have been presented for demonstrating the functions and efficiency of the code. © 2015 Wiley Periodicals, Inc.     

The characteristic polynomials of structures with pending bonds

It is well known [1] that the calculation of characteristic polynomials of graphs of interest in Chemistry which are of any size is usually extremely tedious except for graphs having a vertex of degree 1. This is primarily because of numerous combinations of contributions whether they were arrived at by non-imaginative expansion of the secular determinant or by the use of some of the available graph theoretical schemes based on the enumeration of partial coverings of a graph, etc. An efficient and quite general technique is outlined here for compounds that have pending bonds (i.e., bonds which have a terminal vertex). We have extended here the step-wise pruning of pending bonds developed for acyclic structures by one of the authors [2] for elegant evaluation of the characteristic polynomials of trees by accelerating this process, treating pending group as a unit. Further, it is demonstrated that this generalized pruning technique can be applied not only to trees but to cyclic and polycyclic graphs of any size. This technique reduces the secular determinant to a considerable extent. The present technique cannot handle only polycyclic structures that have no pending bonds. However, frequently such structures can be reduced to a combination of polycyclic graphs with pending bonds [3] so that the present scheme is applicable to these structures too. Thus we have arrived at an efficient and quite a simple technique for the construction of the characteristic polynomials of graphs of any size.