Characteristic polynomials of chemical graphs via symmetric function theory

The characteristic polynomial corresponding to the adjacency matrix of a graph is constructed by using the traces of the powers of the adjacency matrix to calculate the coefficients of the characteristic polynomial via Newton's identities connecting the power sum symmetric functions and the elementary symmetric functions of the eigenvalues. It is shown that Frame's method, very recently employed by Balasubramanian, is nothing but symmetric functions and Newton's identities.     

Pauling bond orders in coronoid hydrocarbons: A general solution

Benzenoid and coronoid systems are considered. A bond order is defined in terms of the elements of the inverse of a skew-symmetric adjacency matrix. It is conjectured that it is identical with the Pauling bond order. A computer program was designed for computing Pauling bond orders of Kekuléan coronoids in general. Numerical examples are given. The skew-symmetric adjacency matrix was exploited for recognition of essentially disconnected coronoid systems. The 29 smallest essentially disconnected coronoids with the phenalene hole are depicted.     

On discerning symmetry properties of graphs

A procedure is outlined which allows the symmetry properties of graphs to be systematically and rigorously investigated. It is based on a search for all the automorphisms of a graph and this is accompanied by suitably applying the procedure for recognizing identical graphs. It consists in finding all the distinctive labeling of the vertices of graph associated with the smallest binary code derived by a particular interpretation of the associated adjacency matrix. No prior cognizance of symmetry operations is required which is in contrast to the usual discussions of the symmetry properties of molecules which are based on the knowledge of pertinent symmetry operations. This is important since in graphs it is neither apparent nor generally possible to simply enlist those permutations of labels which leave the connectivity invariant (i.e., do not alter the form of the adjacency matrix). The procedure is applied to the Petersen graphs and the Desargues-Levi graph, both associated with isomerizations of trigonal bipyramidal complex and other chemical transformations. It is shown that these graphs of high symmetry belong to symmetry groups of order 120 and 240 respectively. The approach can also provide a basis for the development of the symmetry properties of non-rigid molecules in which connectivity is preserved.     

Pairing theorem of graph eigenvalues: Its new proof and a generalization

Each undirected graph has its own adjacency matrix, which is real and symmetric. The negative of the adjacency matrix, also real and symmetric, is a well-defined mathematically elementary concept. By this negative adjacency matrix, the negative of a graph can be defined. Then an orthogonal transformation can be readily found that transforms a negative of an alternant graph to that alternant graph: (?G) → G. Since the procedure does not involve the edge weights, the pairing theorem holds true for all edge-weighted alternant graphs, including the usual “standard” graphs.     

On the evaluation of the characteristic polynomial of a chemical graph

The evaluation of the characteristic polynomial of a chemical graph is considered. It is shown that the operation count of the Le Verrier–Faddeev–Frame method, which is presently considered to be the most efficient method for the calculation of the characteristic polynomial, is of the order n⁴. Here n is the order of the adjacency matrix A or equivalently, the number of vertices in the graph G. Two new algorithms are described which both have the operation count of the order n³. These algorithms are stable, fast, and efficient. A related problem of finding a characteristic polynomial from the known eigenvalues λ_i of the adjacency matrix is also considered. An algorithm is described which requires only n(n ? 1)/2 operations for the solution of this problem.     

Eigenvalues of graphs with threefold symmetry

In many cases, the spectrum of one graph contains the entire spectrum of a second, smaller graph. The larger (composite) graph and the smaller (component) graph are said to be subspectral. Rules are given for constructing two subspectral components of a composite graph which has threefold symmetry such that the eigenvalues of one component and the eigenvalues of the second component taken twice comprise the complete spectrum of the composite graph. The mathematical basis for these rules is shown to be a unitary transformation upon the eigenvalue equation of the adjacency matrix of the composite graph by the matrix which represents threefold rotation.     

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.     

Groups of simple graphs

The group structure of simple graphs can be found by factoring the adjacency matrix into cyclic blocks. The blocks correspond to permutational subgroups of the graph. The overall group structure is a product of the independent subgroups.     

A compact form of the adjacency matrix

It has been shown that the adjacency matrix can be transformed into a row vector and then into a single number. This number can again be decoded to recover the row vector, and this in turn can be decoded to restore the original adjacency matrix. A special, rather efficient coding scheme was devised for acyclic structures.     

Characterization of bond and current correlation structures in a molecular many-electron wave function

A method has been developed to analyzed the bond and current correlation structures of a molecular many-electron wave function. It is shown that the second order density matrix contains information about the bond and current correlations in its off-diagonal components with respect to the indices of orbital basis functions. We break down the off-diagonal correlation functions into five kinds: charge, spin scalar, spin quadrupole, charge spin, and spin polar correlation functions. For a real wave function, the four correlation functions, except for the spin polar one, have only symmetric–symmetric and antisymmetric–antisymmetric components. The former components give site–bond and bond–bond correlations of charges and spins, while the latter components give current–current correlations of charges and spins. The spin polar correlation function has only symmetric–antisymmetric components that give site–current and bond–current correlations of spins. The five off-diagonal correlation functions are expressed in terms of the off-diagonal components of the second order density matrix. The linked off-diagonal correlation functions are defined in that they give dynamical bond and current correlations. The method is applied to the analyses of the bond and current correlations in the low lying exact eigenstates of the PPP Hamiltonian of benzene.     

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.     

Eigenvector and eigenvalues of some special graphs. IV. Multilevel circulants

A multilevel circulant is defined as a graph whose adjacency matrix has a certain block decomposition into circulant matrices. A general algebraic method for finding the eigenvectors and the eigenvalues of multilevel circulants is given. Several classes of graphs, including regular polyhedra, suns, and cylinders can be analyzed using this scheme.     

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.     

The graph center concept for polycyclic graphs

While the concept of the graph center is unambiguous (and quite old) in the case of acyclic graphs, an attempt has been made recently to extend the concept to polycyclic structures using the distance matrix of a graph as the basis. In this work we continue exploring such generalizations considering in addition to the distance matrix, self-avoiding walks or paths as graph invariants of potential interest for discriminating distinctive vertex environments in a graph of polycyclic structures. A hierachy of criteria is suggested that offers a systematic approach to the vertex discrimination and eventually establishes in most cases the graph center as a single vertex, a single bond (edge), or a single group of equivalent vertices. Some applications and the significance of the concept of the graph center are presented.     

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.     

Ground-state properties of benzenoid hydrocarbons by simple bond orbital resonance theory approach

π-electron energies and bond orders of benzenoid hydrocarbons with up to five fused hexagons have been considered by the simple Bond Orbital Resonance Theory (BORT) approach. The corresponding ground states were determined according to four BORT models. In the first three models a diagonalisation of the Hückel-type Hamiltonian was performed in the bases of Kekulé, of Kekulé and mono-Claus and of Kekulé and Claus resonance structures, respectively. In the fourth model a simple BORT ansatz was used. According to this ansatz, the ground state is a linear combination of the positive Kekulé structures, all with equal coefficients. It was shown that π-electron energies and bond orders obtained by these models correlate much better with the PPP energies and bond orders than with the Hückel energies and bond orders. This indicates that a simple BORT approach is quite reliable in predicting the more sophisticated PPP results. Concerning the relative performance of the four BORT models, the best results were obtained with the BORT ansatz. The performance deteriorates with the expansion of the basis set. This is attributed to the fact that in these models the improvement of the basis set is not accompanied with the corresponding improvement of the Hamiltonian. Comparing the BORT-ansatz bond orders with the Pauling bond orders, it was shown that BORT-ansatz bond orders correlate much better with the PPP bond orders. This revised version was published online in July 2006 with corrections to the Cover Date.     

Algorithm for topological correction of lists of simplexes of different dimensions for polyhedration of multicomponent systems

A new algorithm for polyhedration of quaternary and quaternary reciprocal systems is presented. The algorithm is based on checking all the links between vertices of a graph describing the composition diagram and selecting the polyhedration variants that correspond to the relations between the numbers of geometric elements of the complex undergoing polyhedration (graph vertices, links between them, and two-and three-dimensional complexes). Unlike Kraeva’s algorithm based on the decomposition of the graph in terms of zero elements of the adjacency matrix (absent links between vertices), the new algorithm can control the entire polyhedration process, accelerates the search for internal diagonals in the polyhedron, and takes into account their possible competition.     

The spectrum and spanning trees of polyominos on the torus

Polyominos was extensively studied in chemistry and mathematics. The spectrum of a (molecule) graph is the set of eigenvalues of its adjacency matrix. The spectrum and the number of spanning trees of polyominos on the torus are determined in this paper.