Common vertex matrix: A novel characterization of molecular graphs by counting

We present a novel matrix representation of graphs based on the count of equal‐distance common vertices to each pair of vertices in a graph. The element (i, j) of this matrix is defined as the number of vertices at the same distance from vertices (i, j). As illustrated on smaller alkanes, these novel matrices are very sensitive to molecular branching and the distribution of vertices in a graph. In particular, we show that ordered row sums of these novel matrices can facilitate solving graph isomorphism for acyclic graphs. This has been illustrated on all undecane isomers C₁₁H₂₄ having the same path counts (total of 25 molecules), on pair of graphs on 18 vertices having the same distance degree sequences (Slater's graphs), as well as two graphs on 21 vertices having identical several topological indices derived from information on distances between vertices. © 2013 Wiley Periodicals, Inc.     

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.     

Kirchhoff index of linear hexagonal chains

The resistance distance r_ij between vertices i and j of a connected (molecular) graph G is computed as the effective resistance between nodes i and j in the corresponding network constructed from G by replacing each edge of G with a unit resistor. The Kirchhoff index Kf(G) is the sum of resistance distances between all pairs of vertices. In this work, according to the decomposition theorem of Laplacian polynomial, we obtain that the Laplacian spectrum of linear hexagonal chain L_n consists of the Laplacian spectrum of path P_2n+1 and eigenvalues of a symmetric tridiagonal matrix of order 2n + 1. By applying the relationship between roots and coefficients of the characteristic polynomial of the above matrix, explicit closed‐form formula for Kirchhoff index of L_n is derived in terms of Laplacian spectrum. To our surprise, the Krichhoff index of L_n is approximately to one half of its Wiener index. Finally, we show that holds for all graphs G in a class of graphs including L_n. © 2007 Wiley Periodicals, Inc. Int J Quantum Chem, 2008     

Resistance distance in graphs and random walks

We study the resistance distance on connected undirected graphs, linking this concept to the fruitful area of random walks on graphs. We provide two short proofs of a general lower bound for the resistance, or Kirchhoff index, of graphs on N vertices, as well as an upper bound and a general formula to compute it exactly, whose complexity is that of inverting an N×N matrix. We argue that the formulas for the resistance in the case of the Platonic solids can be generalized to all distance‐transitive graphs. © 2001 John Wiley & Sons, Inc. Int J Quant Chem 81: 29–33, 2001     

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 Permanental Polynomials of Some Graphs

Let G be a simple graph with adjacency matrix A(G) and (G,x) the permanental polynomial of G. Let G × H denotes the Cartesian product of graphs G and H. Inspired by Kleins idea to compute the permanent of some matrices (Mol. Phy. 31 (3) (1976) 811–823), in this paper in terms of some orientation of graphs we study the permanental polynomial of a type of graphs. Here are some of our main results.1.If G is a bipartite graph containing no subgraph which is an even subdivision of K _2,3, then G has an orientation G ^e such that (G,x) = det (xI-A(G ^e )), where A(G ^e ) denotes the skew adjacency matrix of G ^e.2.Let G be a 2-connected outerplanar bipartite graph with n vertices. Then there exists a 2-connected outerplanar bipartite graph with 2n+2 vertices such that (G,x) is a factor of .3.Let T be an arbitrary tree with n vertices. Then , where ₁ , ₂ , ..., _n are the eigenvalues of T.     

Bounds for the Kirchhoff index of regular graphs via the spectra of their random walks

Using probabilistic tools, we give tight upper and lower bounds for the Kirchhoff index of any d‐regular N‐vertex graph in terms of d, N, and the spectral gap of the transition probability matrix associated to the random walk on the graph. We then use bounds of the spectral gap of more specialized graphs, available in the literature, in order to obtain upper bounds for the Kirchhoff index of these specialized graphs. As a byproduct, we obtain a closed‐form formula for the Kirchhoff index of the d‐dimensional cube in terms of the first inverse moment of a positive binomial variable. © 2009 Wiley Periodicals, Inc. Int J Quantum Chem, 2010     

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.     

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 new approach for devising local graph invariants: Derived topological indices with low degeneracy and good correlation ability

A new approach is presented for obtaining graph invariants which have very high discriminating ability for different vertices within a graph. These invariants are obtained as the solution set (local invariant set, LOIS) of a system of linear equationsQ · X = R, whereQ is a topological matrix derived from the adjacency matrix of the graph, andR is a column vector which encodes either a topological property (vertex degree, number of vertices in the graph, distance sum) or a chemical property (atomic number). Twenty examples of LOOIs are given and their degeneracy and ordering ability of vertices is discussed. Interestingly, in some cases the ordering of vertices obtained by means of these invariants parallels closely the ordering from an entirely different procedure based on Hierarchically Ordered Extended Connectivities which was recently reported. New topological indices are easily constructed from LOISs. Excellent correlations are obtained for the boiling points and vaporization enthalpies of alkanesversus the topological index representing the sum of local vertex invariants. Les spectacular correlations with NMR chemical shifts, liquid phase density, partial molal volumes, motor octane numbers of alkanes or cavity surface areas of alcohols emphasize, however, the potential of this approach, which remains to be developed in the near future.     

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.     

Distances and volumina for graphs

It has long been realized that connected graphs have some sort of geometric structure, in that there is a natural distance function (or metric), namely, the shortest-path distance function. In fact, there are several other natural yet intrinsic distance functions, including: the resistance distance, correspondent “square-rooted” distance functions, and a so‐called “quasi‐Euclidean” distance function. Some of these distance functions are introduced here, and some are noted not only to satisfy the usual triangle inequality but also other relations such as the “tetrahedron inequality”. Granted some (intrinsic) distance function, there are different consequent graph-invariants. Here attention is directed to a sequence of graph invariants which may be interpreted as: the sum of a power of the distances between pairs of vertices of G, the sum of a power of the “areas” between triples of vertices of G, the sum of a power of the “volumes” between quartets of vertices of G, etc. The Cayley–Menger formula for n-volumes in Euclidean space is taken as the defining relation for so-called “n-volumina” in terms of graph distances, and several theorems are here established for the volumina-sum invariants (when the mentioned power is 2). This revised version was published online in July 2006 with corrections to the Cover Date.     

Details of the reaction graphs for intramolecular isomerizations of the carboranes

From proposed mechanisms for framework reorganizations of the carboranes C₂B _n-2H _n ,n = 5–12, we present reaction graphs in which points or vertices represent individual carborane isomers, while edges or arcs correspond to the various intramolecular rearrangement processes that carry the pair of carbon heteroatoms to different positions within the same polyhedral form. Because they contain both loops and multiple edges, these graphs are actually pseudographs. Loops and multiple edges have chemical significance in several cases. Enantiomeric pairs occur among carborane isomers and among the transition state structures on pathways linking the isomers. For a carborane polyhedral structure withn vertices, each graph hasn(n -1)/2 graph edges. The degree of each graph vertex and the sum of degrees of all graph vertices are independent of the details of the isomerization mechanism. The degree of each vertex is equal to twice the number of rotationally equivalent forms of the corresponding isomer. The total of all vertex degrees is just twice the number of edges orn(n - 1). The degree of each graph vertex is related to the symmetry point group of the structure of the corresponding isomer. Enantiomeric isomer pairs are usually connected in the graph by a single edge and never by more than two edges.     

Resistance distance local rules

In [D.J. Klein, Croat. Chem. Acta. 75(2), 633 (2002)] Klein established a number of sum rules to compute the resistance distance of an arbitrary graph, especially he gave a specific set of local sum rules that determined all resistance distances of a graph (saying the set of local sum rules is complete). Inspired by this result, we give another complete set of local rules, which is simple and also efficient, especially for distance-regular graphs. Finally some applications to chemical graphs (for example the Platonic solids as well as their vertex truncations, which include the graph of Buckminsterfullerene and the graph of boron nitride hetero-fullerenoid B ₁₂ N ₁₂) are made to illustrate our approach.     

Some results on energy of unicyclic graphs with n vertices

A unicyclic graph is a connected graph whose number of edges is equal to the number of vertices. Hou (J Math Chem 29:163–168, 2001) first considered the minimal energy for general unicyclic graphs. In this paper, we determine the unicyclic graphs with the minimal energy in U_n^l{\mathcal {U}_n^l} and the unicyclic graphs with the first forth smallest energy in U_n (n 3 13){\mathcal {U}_n\,(n\geq 13)} vertices.     

Characterization of molecular complexity

We put forward a novel index of molecular complexity, ξ, taking into account the symmetry of a molecular graph and the specificity of structural components considered. The ξ index is defined as the sum of augmented valences of all mutually nonequivalent vertices in a molecular graph. The augmented valence of a vertex in a graph is the sum of its valence and valences of all neighboring vertices with the weight 1/2^d depending on their distance, d, from the vertex. The ξ index is examined on the set of octane isomers and some special classes of graphs. It is also compared with a certain number of alternative complexity measures considered in the literature. © 2002 Wiley Periodicals, Inc. Int J Quantum Chem, 2003