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.     

On the centrality of vertices of molecular graphs

For acyclic systems the center of a graph has been known to be either a single vertex of two adjacent vertices, that is, an edge. It has not been quite clear how to extend the concept of graph center to polycyclic systems. Several approaches to the graph center of molecular graphs of polycyclic graphs have been proposed in the literature. In most cases alternative approaches, however, while being apparently equally plausible, gave the same results for many molecules, but occasionally they differ in their characterization of molecular center. In order to reduce the number of vertices that would qualify as forming the center of the graph, a hierarchy of rules have been considered in the search for graph centers. We reconsidered the problem of “the center of a graph” by using a novel concept of graph theory, the vertex “weights,” defined by counting the number of pairs of vertices at the same distance from the vertex considered. This approach gives often the same results for graph centers of acyclic graphs as the standard definition of graph center based on vertex eccentricities. However, in some cases when two nonequivalent vertices have been found as graph center, the novel approach can discriminate between the two. The same approach applies to cyclic graphs without additional rules to locate the vertex or vertices forming the center of polycyclic graphs, vertices referred to as central vertices of a graph. In addition, the novel vertex “weights,” in the case of acyclic, cyclic, and polycyclic graphs can be interpreted as vertex centralities, a measure for how close or distant vertices are from the center or central vertices of the graph. Besides illustrating the centralities of a number of smaller polycyclic graphs, we also report on several acyclic graphs showing the same centrality values of their vertices. © 2013 Wiley Periodicals, Inc.     

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.     

Unusual random walks

For most structures (molecules, graphs, lattices) a count of random walks for nonequivalent sites will give different numbers, particularly for walks of many steps. Occasionally one finds the same count of walks for nonequivalent sites. These have been termed “unusual walks” and have been closely examined in the case of trivalent graphs. While it remains to be understood what structural factors are critical, some regularities have been observed and are discussed. Unusual walks within a single structure signal “isospectural” points in a graph. A number of structures possessing unusual walks have been displayed, and a few constructive steps which do not alter the “unusual” characteristics of selected vertices have been indicated.     

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.     

Molecular graphs as topological objects in space

Stereochemistry deals primarily with distinctions based on rigid geometry, e.g., bond angles and lengths. But some chemical species have molecular graphs (such as knots, catenanes, and nonplanar graphs K₅ and K_3.3) that reside in space in a topologically nontrivial way. For such molecules there is hope of using topological methods to gain chemical information. Viewing a molecular graph as a topological object in space makes it unrealistically flexible; but if one proves that a certain graph is “topologically chiral” or that two graphs are “topological diastereomers,” then one has ruled out interconversion under any physical conditions for which the molecular graph still makes sense. In this paper, we consider several kinds of topological questions one might ask about graphs in space, methology and results available, and specific topological properties of various molecules.     

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.     

Discrimination of isomeric structures using information theoretic topological indices

Three newly defined information theoretic topological indices, namely “degree complexity (I^d),” “graph vertex complexity (H^V),” and “graph distance complexity (H^D)” along with three other information indices have been used to study their discriminating power of 45 trees and 19 monocyclic graphs. It is found that the newly defined indices have satisfactory discriminating power while H^D has been found to be the only index to discriminate all the graphs studied.     

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.     

S5 graphs as model systems for icosahedral Jahn–Teller problems

The degeneracy of the eigenvalues of the adjacency matrix of graphs may be broken by non-uniform changes of the edge weights. This symmetry breaking is the graph-theoretical equivalent of the molecular Jahn–Teller effect (Ceulemans et al. in Proc Roy Soc 468:971–989, 2012). It is investigated for three representative graphs, which all have the symmetric group on 5 elements, S ₅ , as automorphism group: the complete graph K₅, with 5 nodes, the Petersen graph, with 10 nodes, and an extended K₅ graph with 20 nodes. The spectra of these graphs contain fourfold, fivefold, and sixfold degenerate manifolds, respectively, and provide model systems for the study of the Jahn–Teller effect in icosahedral molecules. The S ₅ symmetries of the distortion modes of the quintuplet in the Petersen graph yield a resolution of the product multiplicity in the corresponding $ H \otimes \left( {g + 2h} \right) $ icosahedral Jahn–Teller problem. In the extended Petersen graph with 20 nodes, a selection rule prevents the Jahn–Teller splitting of the sextuplet into two conjugate icosahedral triplets.     

Molecular graph convolutions: moving beyond fingerprints

Molecular “fingerprints” encoding structural information are the workhorse of cheminformatics and machine learning in drug discovery applications. However, fingerprint representations necessarily emphasize particular aspects of the molecular structure while ignoring others, rather than allowing the model to make data-driven decisions. We describe molecular graph convolutions, a machine learning architecture for learning from undirected graphs, specifically small molecules. Graph convolutions use a simple encoding of the molecular graph—atoms, bonds, distances, etc.—which allows the model to take greater advantage of information in the graph structure. Although graph convolutions do not outperform all fingerprint-based methods, they (along with other graph-based methods) represent a new paradigm in ligand-based virtual screening with exciting opportunities for future improvement.     

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.     

Dynamic light scattering by polyelectrolyte solutions

A generalized expression for the apparent diffusion coefficient (D_app) for macroions as a function of scattering vector (q) is developed. Mathematica®, a system of doing mathematics on a computer, was used to obtain the eigenvalues for a select set of polyion-electrolyte systems. It is shown that under the conditions of low electrolyte concentration D_app exhibits a marked q-dependence. The second part of this communication focuses on the so-called “ordinary-extraordinary” transition observed in some polyelectrolyte systems. The characteristic D_app versus electrolyte profile for this transition is compared with the “splitting” of relaxation times reported for many other polyelectrolyte systems. General problems associated with dynamic light scattering studies on macroion systems are discussed.     

Minimal energy of unicyclic graphs of a given diameter

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. For a given positive integer d with , we characterize the graphs with minimal energy in the class of unicyclic graphs with n vertices and a given diameter d.      

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     

Eigenvalue distributions in alternant hydrocarbons

A theorem due to Lord Rayleigh is applied to the graphs and bual graphs of conjugated hydrocarbon molecules to show how the distribution of their eigenvalues can be understood. A lower bound to the number of eigenvalues larger than or equal to 2 can be predicted easily from the graphs. The uses of the theorem as applied to polyenes, non-alternants and polyhex are illustrated.     

Structural covariance of graphs

Algebraic structures including multiple rank tensors, linear and non-linear operators are related to and represented with various types of graphs. Special emphasis is placed on linear operators e.g. on the Hibert space. A different graph represents the same operator depending on the basis frame used, in general non-orthonormal. All such graphs are shown to belong in one equivalence class and are termed structurally covariant. Crucial indices related to eigenvalues but invariant under any basis frame changes including non-orthonormal ones provide one way to characterize each class. A set of rules are given that allow one to find the graphs structurally covarinat with a given one and/or to deduce the class indices directly by simple pictorial manipulations on a graph. Applications in various fields including the quantum theory of molecules and reactions are indicated.