On geometric-arithmetic index

The geometric-arithmetic (GA) index is a newly proposed graph invariant in mathematical chemistry. We give the lower and upper bounds for GA index of molecular graphs using the numbers of vertices and edges. We also determine the n-vertex molecular trees with the minimum, the second and the third minimum, as well as the second and the third maximum GA indices.     

On reciprocal reverse Wiener index

We report some properties, especially bounds for the reciprocal reverse Wiener index of a connected (molecular) graph. We find that the reciprocal reverse Wiener index possesses the minimum values for the complete graph in the class of n-vertex connected graphs and for the star in the class of n-vertex trees, and the maximum values for the complete graph with one edge deleted in the class of n-vertex connected graphs and for the tree obtained by attaching a pendant vertex to a pendant vertex of the star on n − 1 vertices in the class of n-vertex trees. These results are compared with those obtained for the ordinary Wiener index.     

Bounds on Harary index

In this paper, we obtain the lower and upper bounds on the Harary index of a connected graph (molecular graph), and, in particular, of a triangle- and quadrangle-free graphs in terms of the number of vertices, the number of edges and the diameter. We give the Nordhaus–Gaddum-type result for Harary index using the diameters of the graph and its complement. Moreover, we compare Harary index and reciprocal complementary Wiener number for graphs.     

Hyper-Wiener index for acyclic structures

The discriminating ability of the hyper-Wiener index (the ability to discriminate between isomers) is discussed on a class of acyclic structures (trees) including the molecular graphs of alkanes. For trees with 4 to 26 vertices, numerical data on the classes of trees with coincident indices were obtained. For classes with maximal power, the diagrams of the corresponding trees are presented. Using the index for processing chemical structural data is discussed. Translated fromZhurnal Strukturnoi Khimii, Vol. 40, No. 2, pp. 351–357, March–April, 1999.     

Augmented Zagreb index

Inspired by recent work on the atom-bond connectivity (ABC) index we propose here a new topological index, augmented Zagreb index (AZI). The tight upper and lower bounds for chemical trees are obtained. Moreover, it has been shown that among all trees the star has the minimum AZI value. Characterizing trees with maximal augmented Zagreb index remains an open problem for future research.     

Graph theoretical classification and coding of chemical reactions with a linear mechanism

Linear mechanisms of catalytic and noncatalytic chemical reactions which are theoretically feasible have been classified and coded using a detailed procedure for the unique numbering of cycles, edges, and vertices in the kinetic graphs. The following classification criteria are used in a hierarchical order: number of cycles and vertices, mutual connectivity of the cycles, manner of linking any pair of cycles, number of elements linking two cycles, mutual position of two cycles joined to a third one, orientation of edges, and presence of pendant vertices. All the types and classes of mechanisms are presented for reactions having up to five and four routes, respectively.     

On the difference between atom‐bond connectivity index and Randić index of binary and chemical trees

This article is devoted to establishing some extremal results with respect to the difference of two well‐known bond incident degree indices [atom‐bond connectivity (ABC ) index and Randi? (R ) index] for the chemical graphs representing alkanes. More precisely, the first three extremal trees with respect to ABC – R are characterized among all n‐vertex binary trees (the trees with maximum degree at most 3). The n‐vertex chemical trees (the trees with maximum degree at most 4) having the first three maximum ABC – R values are also determined.     

On reciprocal molecular topological index

We report some properties of the reciprocal molecular topological index RMTI of a connected graph, and, in particular, its relationship with the first Zagreb index M₁. We also derive the upper bounds for RMTI in terms of the number of vertices and the number of edges for various classes of graphs, including K _r+1 -free graphs with r ≥ 2, quadrangle-free graphs, and cacti. Additionally, we consider a Nordhaus-Gaddum-type result for RMTI.     

Wiener indices of trees and monocyclic graphs with given bipartition

The Wiener index of a connected graph is defined as the sum of distances between all unordered pairs of its vertices. It has found various applications in chemical research. We determine the minimum and the maximum Wiener indices of trees with given bipartition and the minimum Wiener index of monocyclic graphs with given bipartition, respectively. We also characterize the graphs whose Wiener indices attain these values. © 2011 Wiley Periodicals, Inc. Int J Quantum Chem, 2012     

QSPR modeling: graph connectivity indices versus line graph connectivity indices

Five QSPR models of alkanes were reinvestigated. Properties considered were molecular surface-dependent properties (boiling points and gas chromatographic retention indices) and molecular volume-dependent properties (molar volumes and molar refractions). The vertex- and edge-connectivity indices were used as structural parameters. In each studied case we computed connectivity indices of alkane trees and alkane line graphs and searched for the optimum exponent. Models based on indices with an optimum exponent and on the standard value of the exponent were compared. Thus, for each property we generated six QSPR models (four for alkane trees and two for the corresponding line graphs). In all studied cases QSPR models based on connectivity indices with optimum exponents have better statistical characteristics than the models based on connectivity indices with the standard value of the exponent. The comparison between models based on vertex- and edge-connectivity indices gave in two cases (molar volumes and molar refractions) better models based on edge-connectivity indices and in three cases (boiling points for octanes and nonanes and gas chromatographic retention indices) better models based on vertex-connectivity indices. Thus, it appears that the edge-connectivity index is more appropriate to be used in the structure-molecular volume properties modeling and the vertex-connectivity index in the structure-molecular surface properties modeling. The use of line graphs did not improve the predictive power of the connectivity indices. Only in one case (boiling points of nonanes) a better model was obtained with the use of line graphs.     

A linear algorithm for the Hyper-Wiener index of chemical trees

An algorithm with a complexity linear in the number of vertices is proposed for the computation of the Hyper-Wiener index of chemical trees. This complexity is the best possible. Computational experience for alkanes is reported.     

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.     

Deletion and contraction identities for the resistance values and the Kirchhoff index

We establish identities, which we call deletion and contraction identities, for the resistance values on an electrical network. As an application of these identities, we give an upper bound to the Kirchhoff index of a molecular graph. Our upper bound, expressed in terms of the set of vertices and the edge connectivity of the graph, improves previously known upper bounds. © 2010 Wiley Periodicals, Inc. Int J Quantum Chem, 2010     

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.     

Partition distance in graphs

If G is a graph and \(\mathcal{P}\) is a partition of V(G), then the partition distance of G is the sum of the distance between all pairs of vertices that lie in the same part of \(\mathcal{P}\). This concept generalizes several metric concepts and is dual to the concept of the colored distance due to Dankelmann, Goddard, and Slater. It is proved that the partition distance of a graph can be obtained from the Wiener index of weighted quotient graphs induced by the transitive closure of the Djokovi?–Winkler relation as well as by any partition coarser than it. It is demonstrated that earlier results follow from the obtained theorems. Applying the main results, upper bounds on the partition distance of trees with prescribed order and radius are proved and corresponding extremal trees characterized.     

Computing weighted Szeged and PI indices from quotient graphs

The weighted (edge-)Szeged index and the weighted (vertex-)PI index are modifications of the (edge-)Szeged index and the (vertex-)PI index, respectively, because they take into account also the vertex degrees. As the main result of this article, we prove that if G is a connected graph, then all these indices can be computed in terms of the corresponding indices of weighted quotient graphs with respect to a partition of the edge set that is coarser than the Θ^*-partition. If G is a benzenoid system or a phenylene, then it is possible to choose a partition of the edge set in such a way that the quotient graphs are trees. As a consequence, it is shown that for a benzenoid system, the mentioned indices can be computed in sublinear time with respect to the number of vertices. Moreover, closed formulas for linear phenylenes are also deduced.     

Computer generation of acyclic graphs based on local vertex invariants and topological indices. Derived canonical labelling and coding of trees and alkanes

A new procedure (GENLOIS) is presented for generating trees or certain classes of trees such as 4-trees (graphs representing alkanes), identity trees, homeomorphical irreducible trees, rooted trees, trees labelled on a certain vertex (primary, secondary, tertiary, etc.). The present method differs from previous procedures by differentiating among the vertices of a given parent graph by means of local vertex invariants (LOVIs). New graphs are efficiently generated by adding points and/or edges only to non-equivalent vertices of the parent graph. Redundant generation of graphs is minimized and checked by means of highly discriminating, recently devised topological indices based either on LOVIs or on the information content of LOVIs. All trees onN + 1 (N + 1 < 17) points could thus be generated from the complete set of trees onN points. A unique cooperative labelling for trees results as a consequence of the generation scheme. This labelling can be translated into a code for which canonical rules were recently stated by A.T. Balaban. This coding appears to be one of the best procedures for encoding, retrieving or ordering the molecular structure of trees (or alkanes).Dedicated to Professor Alexandru T. Balaban on the occasion of his 60th anniversary.