Topological analysis of some special classes of graphs. II. steps,ladders, cylinders

A general strategy is proposed for generating the eigenvectors and the eigenvalues of some special classes of graphs from the well-known chemical graphs such as lines and cycles which are isomorphic to the hydrogen-suppressed linear and cyclic polyenes. This method is applied to step graphs, ladders, cylinders, etc. Net sign analyses are then performed for all these special classes of graphs.     

Two new graph-theoretical methods for generation of eigenvectors of chemical graphs

Two new graph-theoretical methods, (A) and (B), have been devised for generation of eigenvectors of weighted and unweighted chemical graphs. Both the methods show that not only eigenvalues but also eigenvectors have full combinatorial (graph-theoretical) content. Method (A) expresses eigenvector components in terms of Ulam’s subgraphs of the graph. For degenerate eigenvalues this method fails, but still the expressions developed yield a method for predicting the multiplicities of degenerate eigenvalues in the graph-spectrum. Some well-known results about complete graphs (K _n) and annulenes (C _n ), viz. (i)K _n has an eigenvalue −1 with (n−1)-fold degeneracy and (ii) C _n cannot show more than two-fold degeneracy, can be proved very easily by employing the eigenvector expression developed in method (A). Method (B) expresses the eigenvectors as analytic functions of the eigenvalues using the cofactor approach. This method also fails in the case of degenerate eigenvalues but can be utilised successfully in case of accidental degeneracies by using symmetry-adapted linear combinations. Method (B) has been applied to analyse the trend in charge-transfer absorption maxima of the some molecular complexes and the hyperconjugative HMO parameters of the methyl group have been obtained from this trend.     

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.     

Close-to-zero eigenvalues of the rooted product of graphs

Journal of Mathematical Chemistry - The construction of vertex-decorated graphs can be used to produce derived graphs with specific eigenvalues from undecorated graphs, which themselves do not have...     

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.     

A perturbation approach to finite difference methods

A perturbation theoretic approach to finite difference methods for the calculation of eigenvalues is shown to permit an increase in the accuracy of the calculations and also to make possible the calculation of expectation values along with the eigenvalues. An application of the virial theorem can then boost the order of accuracy of any given finite difference method. Integrated probabilities and point values of the normalized wavefunction can be found without any use of quadratures. Illustrative examples are given involving the Schrodinger equation for simple polynomial potentials.     

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.     

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     

Cubic polyhedral Ramanujan graphs with face size no larger than six

A k-regular graph is Ramanujan if its second largest eigenvalue (by magnitude) has magnitude less than or equal to \({2\sqrt{k-1}}\). Exhaustive search up to the bound of 138 vertices, derived from Spielman and Teng’s work on graph partitioning, finds all cubic polyhedral Ramanujan graphs with positive curvature, i.e., with face sizes no larger than 6. Of all such polyhedra, those with face sizes 5 or 6, i.e., fullerenes, give the largest known examples of cubic Ramanujan polyhedra (with 84 vertices). We also consider the notions of negative and positive Ramanujan graphs, as those without eigenvalues in the respective open intervals \({(-k,-2\sqrt{k-1})}\) and \({(2\sqrt{k-1},k)}\). Our results give the full list of positive cubic polyhedral Ramanujan graphs with positive curvature but for negative Ramanujan graphs we have only a finiteness theorem and a conjectured complete list.     

On subspectral acyclic molecular graphs

Based on the contraction and expansion of graphs, the subspectrality of acyclic molecular graphs is treated in a systematic way. The graphs containing eigenvalues 0, t 1 and ± 2 are discussed in detail, with emphasis on how to detect and construct the concealed species which can neither be recognized by symmetry considerations nor by the Heilbronner procedure. As a consequence, graphs and their counts have been given for species with numbers of vertices less than 16.Also known as Yuan-sun Kiang.     

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.     

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.     

The calculation of heavy atom ionization potentials by the relativistic transition state approximation

The relativistic statistical exchange (Xα) model has been applied to the calculation of the ionization potentials of uranium and thorium. The results are comparable in accuracy to those of the relativistic Hartree-Fock method, if the transition state approximation is used, rather than interpreting the eigenvalues by Koopmans' theorem.     

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.     

On the random walk of energy to traps in disordered systems

Adams recently derived a theorem concerning solutions of the Schrödinger equation for an N-electron system. From this theorem he concludes that exact eigenvalues and (antisymmetric) eigenfunctions can be obtained by solving a different type of equation whose eigenfunctions are not antisymmetric. We critically discuss aspects of Adams' formalism.     

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.     

A Pascal type triangle for the number of topologically distinct many-electron Feynman graphs

By expressing the Green function for a many-body system in terms of a perturbative expansion written as a sutra over all connected and topologically distinct Feynnian graphs, it is shown that the number of such diagrams can be iteratively obtained from a Pascal-type triangle, The key to the problem is to notice that it is possible to define on the set of graphs an equivalence relation, and that, from a well-known theorem of set theory, an equivalence relation on a set partitions it into disjoint classes.     

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.     

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.