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.     

A novel nomenclature of polycyclic aromatic hydrocarbons without using graph centre

In this paper, we develop a novel adjacency matrix, He-matrix, corresponding to the dualist graph. Without using the graph center concept, we advance a novel nomenclature of polycyclic aromatic hydrocarbons. Further, we derive some distinguishing theorems about PAH molecules and present some results of our automatic derivatization and automatic classification counting of fused PAH molecules.     

The characteristic polynomials of structures with pending bonds

It is well known [1] that the calculation of characteristic polynomials of graphs of interest in Chemistry which are of any size is usually extremely tedious except for graphs having a vertex of degree 1. This is primarily because of numerous combinations of contributions whether they were arrived at by non-imaginative expansion of the secular determinant or by the use of some of the available graph theoretical schemes based on the enumeration of partial coverings of a graph, etc. An efficient and quite general technique is outlined here for compounds that have pending bonds (i.e., bonds which have a terminal vertex). We have extended here the step-wise pruning of pending bonds developed for acyclic structures by one of the authors [2] for elegant evaluation of the characteristic polynomials of trees by accelerating this process, treating pending group as a unit. Further, it is demonstrated that this generalized pruning technique can be applied not only to trees but to cyclic and polycyclic graphs of any size. This technique reduces the secular determinant to a considerable extent. The present technique cannot handle only polycyclic structures that have no pending bonds. However, frequently such structures can be reduced to a combination of polycyclic graphs with pending bonds [3] so that the present scheme is applicable to these structures too. Thus we have arrived at an efficient and quite a simple technique for the construction of the characteristic polynomials of graphs of any size.     

The overall Wiener index--a new tool for characterization of molecular topology.

Recently, the concept of overall connectivity of a graph G, TC(G), was introduced as the sum of vertex degrees of all subgraphs of G. The approach of more detailed characterization of molecular topology by accounting for all substructures is extended here to the concept of overall distance OW(G) of a graph G, defined as the sum of distances in all subgraphs of G, as well as the sum of eth-order terms, (e)OW(G), with e being the number of edges in the subgraph. Analytical expressions are presented for OW(G) of several basic classes of graphs. The overall distance is analyzed as a measure of topological complexity in acyclic and cyclic structures. The potential usefulness of the components of this generalized Wiener index in QSPR/QSAR is evaluated by its correlation with a number of properties of C3-C8 alkanes and by a favorable comparison with models based on molecular connectivity indices.     

Graphs whose vertices are graphs with bounded degree: Distance problems

By an f-graph we mean a graph having no vertex of degree greater than f. Let U(n,f) denote the graph whose vertex set is the set of unlabeled f-graphs of order n and such that the vertex corresponding to the graph G is adjacent to the vertex corresponding to the graph H if and only if H is obtainable from G by either the insertion or the deletion of a single edge. The distance between two graphs G and H of order n is defined as the least number of insertions and deletions of edges in G needed to obtain H. This is also the distance between two vertices in U(n,f). For simplicity, we also refer to the vertices in U(n,f) as the graphs in U(n,f). The graphs in U(n,f) are naturally grouped and ordered in levels by their number of edges. The distance nf/2 from the empty graph to an f-graph having a maximum number of edges is called the height of U(n,f). For f =2 and for f≥(n-1)/2, the diameter of U(n,f) is equal to the height. However, there are values of the parameters where the diameter exceeds the height. We present what is known about the following two problems: (1) What is the diameter of U(n,f) when 3≥f<(n-1)/2? (2) For fixed f, what is the least value of n such that the diameter of U(n,f) exceeds the height of U(n,f)?     

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.     

Algebraic characterization of bridged polycyclic compounds

An approach based on the topological distance matrix is used for algebraic characterization of bridged polycyclic compounds. The classical bridged structures which have external bridges between cycles were examined together with the more complicated three-dimensional polycyclic systems regarded as containing internal bridges. Thirteen rules are given for characterizing the main types of structural rearrangements in these compounds. The important topological characteristic of (poly)cyclic systems, the molecular cyclicity, is examined in the polycyclic condensed, spiro- and bridged structures, respectively.     

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.     

烯烃顺反异构的拓扑方法研究

在烯烃的顺式与反式异构体中, 处于碳碳双键两端的顶点间的距离是不同的. 可根据几何原理计算与双键相连的顶点间的空间距离, 并以此构造分子图的修正距离矩阵来区分这种差异.按照我们已报导的顶点度-距离指数(VDI)和边度-距离指数(EDI)的计算方法, 用修正距离矩阵(MD)代替距离矩阵(D), 得到修正的顶点度-距离指数(MVDI)和修正的边度-距离指数(MEDI). 这两个参数能较好地区分烯烃顺反异构体的分子结构信息.对烯烃顺反异构体的沸点(b. p.)、折光率(nD 20)、密度(D20)及摩尔折光率(nM)等物化性质进行定量相关, 得到模型方程的相关系数(R)分别为0.9981、0.9570、0.9884和0.9999. 同时, 交叉验证和随机抽样预测结果表明模型具有良好的稳定性和较强的预测能力.     

Statistical properties of carbon nanostructures

We look at modeling carbon nanostructures from a theoretical graph network view, where a graph has atoms at a vertex and links represent bonds. In this way, we can calculate standard statistical mechanics functions (entropy, enthalpy, and free energy) and matrix indices (Wiener index) of finite structures, such as fullerenes and carbon nanotubes. The Euclidean Wiener index (topographical index) is compared with its topological (standard) counterpart. For many of these parameters, the data have power law behavior, especially when plotted versus the number of bonds or the number of atoms. The number of bonds in a carbon nanotube is linear with the length of the nanotube, thus enabling us to calculate the heat of formation of capped (5,5) and (10,10) nanotubes. These properties are determined from atomic coordinates using MATLAB routines.     

Efficient enumeration of stereoisomers of outerplanar chemical graphs using dynamic programming

Exhaustive and nonredundant generation of stereoisomers of a chemical compound with a specified constitution is an important tool for molecular structure elucidation and molecular design. It is known that many chemical compounds have outerplanar graph structures. In this paper we deal with chemical compounds composed of carbon, hydrogen, oxygen, and nitrogen atoms whose graphical structures are outerplanar and consider stereoisomers caused only by asymmetry around carbon atoms. Based on dynamic programming, we propose an algorithm of generating all stereoisomers without duplication. We treat a given outerplanar graph as a graph rooted at its structural center. Our algorithm first recursively computes the number of stereoisomers of the subgraph induced by the descendants of each vertex and then constructs each stereoisomer by backtracking the process of computing the numbers of stereoisomers. Our algorithm correctly counts the number of stereoisomers in O(n) time and space and correctly enumerates all of the stereoisomers in O(n3) time per stereoisomer on average and in O(n) space, where n is the number of atoms in a given structure.     

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.     

The number of Kekulé structures of polyominos on the torus

Let G be a (molecule) graph. A perfect matching, or Kekulé structure of G is a set of independent edges covering every vertex exactly once. Enumeration of Kekulé structures of a (molecule) graph is interest in chemistry, physics and mathematics. In this paper, we focus on some polyominos on the torus and obtain the explicit expressions on the number of the Kekulé structures of them.     

单硫醚气相色谱保留指数拓扑化学研究

在分子拓扑化学理论的基础上,根据分子中原子的特性,用分子中原子的平衡电负性对分子图进行着色,在距离矩阵的基础上结合分子中各原子的支化度构建一组新的拓扑指数NPm(m=1,2,3),利用多元线性回归技术将单硫醚在4种极性固定相的气相色谱保留指数与NPm(m=1,2,3)建立相应的定量结构-保留相关关系模型(QSRR),并用这种模型对单硫醚的气相色谱保留指数进行预测,结果表明,预测结果和实验值吻合较好。     

A simple algorithm for unique representation of chemical structures-cyclic/acyclic functionalized achiral molecules

An algorithm, based on "vertex priority values" has been proposed to uniquely sequence and represent connectivity matrices of chemical structures of cyclic/acyclic functionalized achiral hydrocarbons and their derivatives. In this method, "vertex priority values" have been assigned in terms of atomic weights, subgraph lengths, loops, and heteroatom contents. Subsequently, the terminal vertices have been considered upon completing the sequencing of the core vertices. This approach provides a multilayered connectivity graph, which can be put to use in comparing two or more structures or parts thereof for any given purpose. Furthermore, the basic vertex connection tables generated here are useful in the computation of characteristic matrices/topological indices and automorphism groups and in storing, sorting, and retrieving chemical structures from databases.     

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     

Distance-restricted matching extendability of fullerene graphs

A fullerene graph is a 3-connected cubic plane graph whose all faces are bounded by 5- or 6-cycles. In this paper, we show that a matching M of a fullerene graph can be extended to a perfect matching if the following hold: (i) three faces around each vertex in \(\{x,y:xy\in M\}\) are bounded by 6-cycles and (ii) the edges in M lie at distance at least 13 pairwise.