Computer generation of distance polynomials of graphs

A computer program is developed to compute distance polynomials of graphs containing up to 200 vertices. The code also computes the eigenvalues and the eigenvectors of the distance matrix. It requires as input only the neighborhood information from which the program constructs the distance matrix. The eigenvalues and eigenvectors are computed using the Givens-Householder method while the characteristic polynomials of the distance matrix are constructed using the codes developed by the author before. The newly developed codes are tested out on many graphs containing large numbers of vertices. It is shown that some cyclic isospectral graphs are differentiated by their distance polynomials although distance polynomials themselves are in general not unique structural invariants.     

Study of the origin of subspectrality in molecular graphs

Summary The subspectral origin of three families of molecules based on cyclobutadiene, benzene, and cyclooctatetraene is discussed. The graph theoretical decomposition of the fourfold cyclooctatetraene molecular graphs is presented in explicit form and has expedited the computation of their respective eigenvalues. The cyclic automorphism approach of Davidson is clarified and merged with the author's methodology leading to a more comprehensive procedure for rapidly determining the characteristic polynomial and eigenvalues of chemically significant molecular graphs. The graph theoretical determination of the characteristic polynomials and eigenvalues of two sixfold coronene-related molecular families is presented.     

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 use of Frame’s method for the characteristic polynomials of chemical graphs

The evaluation of characteristic polynomials of graphs of any size is an extremely tedious problem because of the combinatorial complexity involved in this problem. While particular elegant methods have been outlined for this problem, a general technique for any graph is usually tedious. We show in this paper that the Frame method for the characteristic polynomial of a matrix is extremely useful and can be applied to graphs containing large numbers of vertices. This method reduces the difficult problem of evaluating the characteristic polynomials to a rather simple problem of matrix products. The coefficients in the characteristic polynomial are generated as traces of matrices generated in a recursive product of two matrices. This method provides for an excellent and a very efficient algorithm for computer evaluation of characteristic polynomials of graphs containing a large number of vertices without having to expand the secular determinant of the matrix associated with the graph. The characteristic polynomials of a number of graphs including that of a square lattice containing 36 vertices are obtained for the first time.     

On evaluation of the characteristic polynomial for large molecules

Existing schemes for evaluation of the characteristic polynomial of a graph suffer from limited practicality. Their application to large molecules inordinately increases the amount of labor. Here a procedure is outlined which is useful even for large molecules. It is based on a not widely known property of the collection of characteristic polynomials for Ulam's subgraphs, which, when added, give the derivative of the characteristic polynomial of the initial graph. The characteristic polynomials for Ulam's subgraphs are, as a rule, easier to derive due to the presence of many pending bonds in graphs of chemical interest. The last step requires an integration of a polynomial (which is a straightforward step) and determining the constant of integration, which represents the determinant of the adjacency matrix. The available methods for determing the additive constant (the determinant) are combinatorially much simpler than the initial task of finding all of the coefficients of the characteristic polynomial. The approach is illustrated on selected benzenoid hydrocarbons, nonbenzenoid, and nonalternant systems. Construction of the characteristic polynomials can be accelerated by considering auxiliary fragments and irreducible subgraphs separately and combining them in the final expression. Many auxiliary fragments allow their characteristic polynomials to be expressed in a closed form using recursive relations. The results for complex molecules can thus be written in a relatively compact form. Finally, the derivative of the characteristic polynomial, expressed in terms of selected auxiliary functions and irreducible components, can be integrated directly to give the result in terms of contributions signifying various fragments rather than as an explicit function of x.     

Generation of the eigenvectors of the topological matrix from graph theory

The technique of describing the characteristic polynomial of a graph is here extended to construction of the eigenvectors. Recurrence relations and path tracing are combined to generate eigenvector coefficients as polynomial functions of the eigenvalues. The polynomials are expressed as linear functions of Chebyshev polynomials in order to simplify the computational effort. Particular applications to the Hückel MO theory, including heteroatom effects, are shown.     

Computer generation of the characteristic polynomials of chemical graphs

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of vertices that are neighbors of a given vertex and with labels smaller than the label of that vertex. The program generates and stores only the lower triangle of the adjacency matrix in canonical ordering in a one-dimensional array. The program is written in integer arithmetic, and it can be easily modified to real arithmetic. The coefficients in the characteristic polynomials of several graphs were generated in less than a few seconds, thus solving the difficult problem of generating characteristic polynomials of graphs. The characteristic polynomials of a number of very complicated graphs are obtained including for the first time the characteristic polynomial of an honeycomb lattice graph containing 54 vertices.     

New algorithms for iterative matrix‐free eigensolvers in quantum chemistry

New algorithms for iterative diagonalization procedures that solve for a small set of eigen‐states of a large matrix are described. The performance of the algorithms is illustrated by calculations of low and high‐lying ionized and electronically excited states using equation‐of‐motion coupled‐cluster methods with single and double substitutions (EOM‐IP‐CCSD and EOM‐EE‐CCSD). We present two algorithms suitable for calculating excited states that are close to a specified energy shift (interior eigenvalues). One solver is based on the Davidson algorithm, a diagonalization procedure commonly used in quantum‐chemical calculations. The second is a recently developed solver, called the “Generalized Preconditioned Locally Harmonic Residual (GPLHR) method.” We also present a modification of the Davidson procedure that allows one to solve for a specific transition. The details of the algorithms, their computational scaling, and memory requirements are described. The new algorithms are implemented within the EOM‐CC suite of methods in the Q‐Chem electronic structure program. © 2014 Wiley Periodicals, Inc.     

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.     

Brackets to the eigenvalues of the Schrödinger equation,part 1. Tridiagonal matrices

The problem of upper and lower bounds to the first few eigenvalues of a very large or infinite tridiagonal matrix H is studied. Those eigenvalues of a comparison-matrix M _n which are lower than a characteristic limit, together with the corresponding eigenvalues of the variational matrix H _n are shown to bracket exact eigenvalues of H . M _n differs from H _n only in the last off-diagonal element and is easily obtained from H . Sufficient conditions for lower bounds are based on a low estimate of the characteristic limit. For increasing dimensions n, the lower bounds approach the exact eigenvalues from below. As a numerical illustration, brackets to the known eigenvalues of the harmonic oscillator with a linear perturbation are calculated.     

Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs

Computational algorithms are described which provide for constructing the set of associated edge-weighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or purely imaginary numbers so that the adjacency matrix is hermitian. The computer code developed earlier by one of the authors (K.B.) is generalized for complex hermitian matrices. Applications to bridged and spirographs, some lattices and all polycyclic graphs containing up to four cycles are considered.     

Use of invariants in bounding 2-fermion reduced density matrix eigenvalues

The known bounds on the eigenvalues of 2-Fermion reduced density matrices may be improved by considering unitarily invariant properties of the associated natural geminals and of the system 1-Fermion reduced density matrix. The polynomial invariants are particularly important, since they may be introduced systematically according to the degree of the polynomials.     

On the possibility of analytically continuing stabilization graphs to determine resonance positions and widths accurately

Previous efforts to extract resonance widths by analytic continuation of stabilization graphs were limited by non-analytic behavior of the eigenvalues as functions of the stabilization parameter. We describe a procedure which avoids this difficulty by numerical analytic continuation of the characteristic polynomial, truncated to low order, of the hamiltonian matrix.     

The scaled Hermite–Weber basis in the spectral and pseudospectral pictures

Computational efficiencies of the discrete (pseudospectral, collocation) and continuous (spectral, Rayleigh–Ritz, Galerkin) variable representations of the scaled Hermite–Weber basis in finding the energy eigenvalues of Schrödinger operators with several potential functions have been compared. It is well known that the so-called differentiation matrices are neither skew-symmetric nor symmetric in a pseudospectral formulation of a differential equation, unlike their Rayleigh–Ritz counterparts. In spite of this fact, it is shown here that the spectra of matrix Hamiltonians generated by Hermite collocation method may be determined by way of diagonalizing symmetric matrices. Furthermore, the symmetric matrix elements do not require the evaluation of Hermite polynomials at the grid points. Surprisingly, the present numerical results suggest that the convergence rates of collocation and Rayleigh–Ritz methods are entirely the same.AMS subject classification: 65L60, 81Q05, 65L15, 34L40, 42C10     

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.     

An algebraic approach to the study of the titration curves of weak acids and their mixtures

It is shown that the titration curves of weak acids and their mixtures which have rational mole-fractions of the components can be transformed into polynomials. These protonation polynomials are called normal or abnormal according to whether their coefficients do or do not satisfy certain inequalities derived from statistical considerations. The normality of a second-degree polynomial is shown to be a characteristic equivalent to the reality of its zeros. Protonation polynomials with real zeros are shown to be normal, but the converse of this statement is not necessarily true. The titration curve of a polyfunctional acid is identical with that of an equimolar mixture of monofunctional acids if and only if the protonation polynomial has real zeros. A method for determining the functionality of an acid from its titration curve by using protonation polynomials is outlined.     

The numerical solution of fujita's integral equation to provide estimates of molecular weight distributions

A standard model of the behavior of polymers under ultracentrifugation results in Fujita's equation for their molecular weight distribution. Fujita's and related equations are examples of Fredholm integral equations of the first kind and are thus ill posed. Two methods are described for solving the equations numerically and hence providing estimates of the molecular weight distribution. The first method involves expanding the distribution in terms of orthogonal polynomials whose coefficients are calculated from estimates of the moments of the distribution. In the second method the distribution is reconstructed by using matrix singular-value decomposition techniques combined with an approximant expressed as a sum of B-splines. The potential and practical limitations associated with the methods are illustrated by numerical results from a series of tests on four problems designed to represent distributions with different modal properties.     

The characteristic polynomial of a chemical graph

We list uses of, and the computational methods for the characteristic polynomial of a (chemical) graph. Pour computational methods are singled out for more detailed presentation. These are the graphical methods of Sachs, the recurrence formulae for several classes of simple graphs, the method based on Ulam subgraphs, and the Le Verrier — Faddeev — Franic recursive method. The latter method appears, at present, to be the most efficient procedure for the computation of the characteristic polynomials of graphs of sizes with up to even a few hundred sites.Dedicated to Dennis H. Rouvray, the friend and one of the foremost popularizers of chemical graph theory in our time.Research supported by the Robert A. Welch Foundation of Houston, Texas, USA.     

Quality-assurance procedures for graphite-furnace atomic-absorption spectrometry

A procedure is described for quality-control in graphite-furnace atomic-absorption spectrometry. It uses an NBS standard reference material to avoid errors in standard preparation, and very simple instrumental conditions, with no matrix modifier or pyrolysis step. The characteristic mass and the Zeeman ratio are calculated for Ag, Cu, and Cr, and deviations from the expected values for these quantities are correlated with potential instrumental malfunctions.     

An iterative method to solve the algebraic eigenvalue problem

An iterative method based on perturbation theory in matrix form is described as a procedure to obtain the eigenvalues and eigenvectors of square matrices. Practical vector notation and elementary schematic algorithm codes are given. The particular programming characteristics of the present computational scheme are based upon eigenvector corrections, obtained through a simple Rayleigh–Schrödinger perturbation theory algorithm. The proposed methodological processes can be used to evaluate the eigensystem of large matrices.