Maximally distance-unbalanced trees

Journal of Mathematical Chemistry - For a graph G, and two distinct vertices u and v of G, let $$ n_{{G(u,v)}} $$ be the number of vertices of G that are closer in G to u than to v. Miklavi?...     

Three methods for calculation of the hyper-Wiener index of molecular graphs

The hyper-Wiener index WW of a graph G is defined as WW(G) = (summation operator d (u, v)(2) + summation operator d (u, v))/2, where d (u, v) denotes the distance between the vertices u and v in the graph G and the summations run over all (unordered) pairs of vertices of G. We consider three different methods for calculating the hyper-Wiener index of molecular graphs: the cut method, the method of Hosoya polynomials, and the interpolation method. Along the way we obtain new closed-form expressions for the WW of linear phenylenes, cyclic phenylenes, poly(azulenes), and several families of periodic hexagonal chains. We also verify some previously known (but not mathematically proved) formulas.     

Quest for molecular graphs with maximal energy: a computer experiment

If lambda(1), lambda(2),..., lambda(n) are the eigenvalues of a graph G, then the energy of G is defined as E(G) = the absolute value of lambda(1) + the absolute value of lambda(2) +.... + the absolute value of lambda(n). If G is a molecular graph, representing a conjugated hydrocarbon, then E(G) is closely related to the respective total pi-electron energy. It is not known which molecular graph with n vertices has maximal energy. With the exception of m = n - 1 and m = n, it is not known which molecular graph with n vertices and m edges has maximal energy. To come closer to the solution of this problem, and continuing an earlier study (J. Chem. Inf. Comput. Sci. 1999, 39, 984-996, ref 7), we performed a Monte Carlo-type construction of molecular (n,m)-graphs, recording those with the largest (not necessarily maximal possible) energy. The results of our search indicate that for even n the maximal-energy molecular graphs might be those possessing as many as possible six-membered cycles; for odd n such graphs seem to prefer both six- and five-membered cycles.     

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.     

Determination of the Wiener molecular branching index for the general tree

The many applications of the distance matrix, D(G), and the Wiener branching index, W(G), in chemistry are briefly outlined. W(G) is defined as one half the sum of all the entries in D(G). A recursion formula is developed enabling W(G) to be evaluated for any molecule whose graph G exists in the form of a tree. This formula, which represents the first general recursion formula for trees of any kind, is valid irrespective of the valence of the vertices of G or of the degree of branching in G. Several closed expressions giving W(G) for special classes of tree molecules are derived from the general formula. One illustrative worked example is also presented. Finally, it is shown how the presence of an arbitrary number of heteroatoms in tree-like molecules can readily be accommodated within our general formula by appropriately weighting the vertices and edges of G.     

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)?     

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.     

部分同谱分子

本文在HMO近似内讨论部分同谱分子。认为在一个没有对称面的分子中, 可能隐含着一个对称面。对称面将分子分成两部分。这两部分所表示的共轭体系是部分同谱分子。它们与整个分子也是部分同谱分子。文中讨论了三顶点链图, 这种链图表示了无数个部分同谱分子进行收缩的总结果, 同时用少数例子加以说明。     

Perfect matchings in random pentagonal chains

Let G be a (molecule) graph. A perfect matching, or kekulé structure and dimer covering, in a graph G is a set of pairwise nonadjacent edges of G that spans the vertices of G. In this paper, we obtained the explicit expression for the expectation of the number of perfect matchings in random pentagonal chains. Our result shows that, for any polygonal chain \(Q_{n}\) with odd polygons, the number of perfect matchings can be determined by their concatenation LA-sequence.     

Algorithm for topological correction of lists of simplexes of different dimensions for polyhedration of multicomponent systems

A new algorithm for polyhedration of quaternary and quaternary reciprocal systems is presented. The algorithm is based on checking all the links between vertices of a graph describing the composition diagram and selecting the polyhedration variants that correspond to the relations between the numbers of geometric elements of the complex undergoing polyhedration (graph vertices, links between them, and two-and three-dimensional complexes). Unlike Kraeva’s algorithm based on the decomposition of the graph in terms of zero elements of the adjacency matrix (absent links between vertices), the new algorithm can control the entire polyhedration process, accelerates the search for internal diagonals in the polyhedron, and takes into account their possible competition.     

Growth in catacondensed benzenoid graphs

The generating function of the sequence counting the number of graph vertices at a given distance from the root is called the spherical growth function of the rooted graph. The vertices farthest from the root form an induced subgraph called the distance-residual graph. These mathematical notions are applied to benzenoid graphs which are used in graph theory to represent benzenoid hydrocarbons. An algorithm for calculating the growth in catacondensed benzenoids is presented, followed by some examples.     

Graph theory of synthons

A graph-theory model of synthons is suggested. A synthon is a special kind of the molecular graph in which some vertices are distinguished from other ones, and they are called the virtual vertices. The most important property of the synthons is that the constraint of strict stoichiometry is removed and the virtual vertices formally correspond to functional groups that are not closely specified.     

Trees with the minimum Wiener number

The Wiener number (𝒲) of a connected graph is the sum of distances for all pairs of vertices. As a graphical invariant, it has been found extensive application in chemistry. Considering the family of trees with n vertices and a fixed maximum vertex degree, we derive some methods that can strictly reduce 𝒲 by shifting leaves. And then, by a process, we prove that the dendrimer on n vertices is the unique graph reaching the minimum Wiener number. © 2000 John Wiley & Sons, Inc. Int J Quant Chem 78: 331–340, 2000     

Dendrimer eigen-characteristics

Journal of Mathematical Chemistry - Local graph symmetry groups act in a non-identical fashion on just a proper (local) subset of a graph’s vertices, and consequent theorems for adjacency...     

Ordering trees with given pendent vertices with respect to Merrifield-Simmons indices and Hosoya indices

The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, we order a kind of trees with given number of pendent vertices with respect to Merrifield-Simmons indices and Hosoya indices.     

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     

Topological indices for molecular fragments and new graph invariants

Whereas the internal fragment topological index (IFTI) is calculated in the normal manner as for any molecule, the external fragment topological index (EFTI) is calculated so as to reflect the interaction between the excised fragment F and the remainder of the molecule (G-F). For selected topological indices (TIs), a survey of EFTI values, formulas and examples is presented. Some requirements as to the fragment indices are formulated and examined. In the discussion of the results, it is shown that for some TIs regularities exist in the dependence of EFTI values upon the branching of fragment F, or upon the marginal versus central position of the fragment F in the graph G. New vortex invariants can be computed as EFTI values for one-atom fragments over all graph vertices; by iteration, it is in principle possible to devise an infinite number of now vertex invariants.     

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.     

The Merrifield–Simmons Indices and Hosoya Indices of Trees with <Emphasis Type="Italic">k</Emphasis> Pendant Vertices

The Merrifield–Simmons index of a graph is defined as the total number of the independent sets of the graph and the Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, we characterize the trees with maximal Merrifield–Simmons indices and minimal Hosoya indices, respectively, among the trees with k pendant vertices.