Coulson function and Hosoya index: extension of the relationship to polycyclic graphs and to new types of matching polynomials

Gutman et al. [Chem. Phys. Lett. 355 (2002) 378–382] established a relationship between the Coulson function, , where \phi is the characteristic polynomial, and the Hosoya index Z, which is the sum over all k of the counts of all k-matchings. Like the original Coulson function, this relationship was postulated only for trees. The present study shows that the relationship can be extended to (poly)cyclic graphs by substituting the matching, or acyclic, polynomial for the characteristic polynomial. In addition, the relationship is extended to new types of matching polynomials that match cycles larger than edges (2-cyc1es). Finally, this presentation demonstrates a rigorous mathematical relationship between the graph adjacency matrices and the coefficients of these polynomials and describes computational algorithms for calculating them.     

Generalized Hosoya polynomials of hexagonal chains

Similar to the well-known Wiener index, Eu et al. [Int. J. Quantum Chem. 106 (2006) 423–435] introduced three families of topological indices including Schultz index and modified Schultz index, called generalized Wiener indices, and gave the similar formulae of generalized Wiener indices of hexagonal chains. They also mentioned three families of graph polynomials in x, called generalized Hosoya polynomials in contrast to the (standard) Hosoya polynomial, such that their first derivatives at x = 1 are equal to generalized Wiener indices. In this note we gave explicit analytical expressions for generalized Hosoya polynomials of hexagonal chains.     

Immanants and immanantal polynomials of chemical graphs

The much-studied determinant and characteristic polynomial and the less well-known permanent and permanental polynomial are special cases of a large class of objects, the immanants and immanantal polynomials. These have received some attention in the mathematical literature, but very little has appeared on their applications to chemical graphs. The present study focuses on these and also generalizes the acyclic or matching polynomial to an equally large class of acyclic immanantal polynomials, generalizes the Sachs theorem to immanantal polynomials, and sets forth relationships between the immanants and other graph properties, namely, Kekulé structure count, number of Hamiltonian cycles, Clar covering polynomial, and Hosoya sextet polynomial.     

Fibonacci relations. On the computation of some counting polynomials of very large graphs

A definition of a set of Fibonacci graphs is introduced which allows construction of several counting polynomials of very large graphs quite easily using a pencil-and-a-paper approach. These polynomials include matching, sextet, independence, Aihara and Hosoya polynomials. Certain combinatorial properties of Kekulé counts of benzenoid hydrocarbons are given. A relation to a new topological function that counts the cardinality of graph topology [23] is given.Dedicated to Professor Oskar E. Polansky for his enthusiastic support, participation and promotion of chemical graph theory.     

Computer generation of king and color polynomials of graphs and lattices and their applications to statistical mechanics

A computer program is developed in Pascal for the generation of king and color polynomials of graphs. The king polynomial was defined by Motoyama and Hosoya and was shown to be useful in dimer statistics, enumeration of Kekulé structures, etc. We show that the king polynomial of a lattice is the same as the color polynomial of the associated dualist graph, where the color polynomial is defined here as the number of ways of coloring the vertices of a graph with one type of color (say, green) such that two adjacent vertices are not colored with the same color. Applications of these polynomials to exact finite method of lattice statistics are outlined.     

Hosoya polynomials of armchair open‐ended nanotubes

For a connected graph G we denote by d(G,k) the number of vertex pairs at distance k. The Hosoya polynomial of G is H(G,x) = ∑_k≥0 d(G,k)x^k. In this paper, analytical formulae for calculating the polynomials of armchair open‐ended nanotubes are given. Furthermore, the Wiener index, derived from the first derivative of the Hosoya polynomial in x = 1, and the hyper‐Wiener index, from one‐half of the second derivative of the Hosoya polynomial multiplied by x in x = 1, can be calculated. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2007     

A graphical evaluation of characteristic polynomials of huckel trees

Characteristic polynomials of acyclic carbon chains (Huckel trees) are treated in a systematic way. Formulas of coefficients (a_k) of the polynomial are obtained in terms of connectivities that were introduced for dealing with moments in a previous paper. Based on the meaning of a_k, a graph-theoretical analysis is given such that a_k can be expressed as a linear combination of binomial factors specified by a set of graphs containing ½k edges. The numerical relationship is disclosed between each binomial factor and its specified graph. This stimulates the proposal of a novel approach for evaluating ak by simply collecting the graph set of defnite edges. The approach is equally applicable for the evaluation of matching polynomials of cyclic systems and extendable to the investigation of general trees.     

Conjugated chemical trees with minimal energy and prescribed diameter

The energy of a molecular graph G is defined as the sum of the absolute values of the eigenvalues of A(G), where A(G) is the adjacency matrix of this graph. This article characterizes conjugated chemical trees with prescribed diameter and minimal energies and presents explicit expressions of their Hosoya indices. © 2006 Wiley Periodicals, Inc. Int J Quantum Chem, 2006     

Hosoya polynomials of TUC4C8(R) nanotubes

For a connected graph G, the Hosoya polynomial of G is defined as H(G, x) = ∑_{u,v}?V(G)x^{d(u, v)}, where V(G) is the set of all vertices of G and d(u,v) is the distance between vertices u and v. In this article, we obtain analytical expressions for Hosoya polynomials of TUC₄C₈(R) nanotubes. Furthermore, the Wiener index and the hyper‐Wiener index can be calculated. © 2008 Wiley Periodicals, Inc. Int J Quantum Chem, 2009     

Application of the unitary group approach to evaluate spin density for configuration interaction calculations in a basis of S2 eigenfunctions

We present an implementation of the spin‐dependent unitary group approach to calculate spin densities for configuration interaction calculations in a basis of spin symmetry‐adapted functions. Using S² eigenfunctions helps to reduce the size of configuration space and is beneficial in studies of the systems where selection of states of specific spin symmetry is crucial. To achieve this, we combine the method to calculate U(n) generator matrix elements developed by Downward and Robb (Theor. Chim. Acta 1977, 46, 129) with the approach of Battle and Gould to calculate U(2n) generator matrix elements (Chem. Phys. Lett. 1993, 201, 284). We also compare and contrast the spin density formulated in terms of the spin‐independent unitary generators arising from the group theory formalism and equivalent formulation of the spin density representation in terms of the one‐ and two‐electron charge densities.     

On the matching polynomials of graphs with small number of cycles of even length

Suppose that G is a simple graph. We prove that if G contains a small number of cycles of even length then the matching polynomial of G can be expressed in terms of the characteristic polynomials of the skew adjacency matrix A(G^e) of an arbitrary orientation G^e of G and the minors of A(G^e). In addition to a formula previously discovered by Godsil and Gutman, we obtain a different formula for the matching polynomial of a general graph. © 2005 Wiley Periodicals, Inc. Int J Quantum Chem, 2005     

A parallelized integral-direct second-order Møller–Plesset perturbation theory method with a fragment molecular orbital scheme

We propose a parallelized integral-direct algorithm of the second-order Møller–Plesset perturbation theory (MP2) as a size-consistent correlated method. The algorithm is a modification of the recipe by Mochizuki et al. [(1996) Theor Chim Acta 93:211]. There is no need to communicate the bulky data of integrals across worker processes, keeping the formal fifth-power dependence on the number of basis functions. A multiple integral screening procedure is incorporated to reduce the operation costs effectively. An approximate MP2 density matrix can also be directly calculated through the integral contraction with orbital energies. We implement the MP2 code by accepting Kitauras fragment molecular orbital (FMO) scheme as in the program ABINIT-MP developed by Nakano et al. [(2002) Chem Phys Lett 351:475]. The error in the FMO–MP2 energies is found to be within the order of the chemical accuracy. Timing and parallel acceleration results are shown for test molecules.     

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.     

Theory and computational applications of Fibonacci graphs

The concept of Fibonacci graphs introduced and developed by this author is critically reviewed. The concept has been shown to provide an easypencil-and-paper method of calculating characteristic, matching, counting, sextet, rook, color and king polynomials of graphs of quite large size with limited connectivities. For example, the coefficients of the matching polynomial of 18-annuleno—18-annulene can be obtainedby hand using the definition of Fibonacci graphs. They are (in absolute magnitudes): 1, 35, 557, 5337, 34 361, 157 081, 525 296, 1304 426, 2 416 571, 3 327 037, 3 362 528, 2 440 842, 1 229 614, 407 814, 81936, 8652, 361, 3. The theory of Fibonacci graphs is reviewed in an easy and detailed language. The theory leads to modulation of the polynomial of a graph with the polynomial of a path.Dedicated to Professor R. Bruce King for his enthusiastic promotion and contributions to Mathematical Chemistry.     

Computer generation of characteristic polynomials of edge-weighted graphs,heterographs, and directed graphs

The computer code developed previously (K. Balasubramanian, J. Computational Chem., 5 , 387 (1984)) for the characteristic polynomials of ordinary (nonweighted) graphs is extended in this investigation to edge-weighted graphs, heterographs (vertex-weighted), graphs with loops, directed graphs, and signed graphs. This extension leads to a number of important applications of this code to several areas such as chemical kinetics, statistical mechanics, quantum chemistry of polymers, and unsaturated systems containing heteroatoms which include bond alternation. The characteristic polynomials of several edgeweighted graphs which may represent conjugated systems with bond alternations, heterographs (molecules with heteroatoms), directed graphs (chemical reaction network), and signed graphs and lattices are obtained for the first time.     

The proof of a conjecture concerning acyclic molecular graphs with maximal Hosoya index and diameter 4

The Hosoya index of a graph is defined as the total number of the matchings of the graph. In this paper, we solve a conjecture in Ou, J. Math. Chem, DOI: 10.1007/S10910-006-9199-1 concerning acyclic molecular graphs with maximal Hosoya index and diameter 4. Partially supported by NNSFC (No. 10571105, 10671081).     

Computer generation of the characteristic polynomials of chemical graphs

A computer program based on the Frame method for the characteristic polynomials of graphs is developed. This program makes use of an efficient polynomial algorithm of Frame for generating the coefficients in the characteristic polynomials of graphs. This program requires as input only the set of vertices that are neighbors of a given vertex and with labels smaller than the label of that vertex. The program generates and stores only the lower triangle of the adjacency matrix in canonical ordering in a one-dimensional array. The program is written in integer arithmetic, and it can be easily modified to real arithmetic. The coefficients in the characteristic polynomials of several graphs were generated in less than a few seconds, thus solving the difficult problem of generating characteristic polynomials of graphs. The characteristic polynomials of a number of very complicated graphs are obtained including for the first time the characteristic polynomial of an honeycomb lattice graph containing 54 vertices.     

Novel graph-theoretical approach to estimating the relative importance of individual Kekulé valence structures. II. Benzenoid systems having four to seven fused benzene rings: “Pseudodegenerate” states

Kekulé structures of 10 nonlinear acenes comprising 83 graphs are studied through the use of connectivities [M. Randi?, J. Am. Chem. Soc. 97 , 6609 (1975)] of their corresponding submolecules [H. Joela, Theor. Chim. Acta 39 , 241 (1975)]. In certain rare cases states were identified to have identical branching indices but different Kekulé indices [A. Graovac, I. Gutman, M. Randi?, and N. Trinajsti?, J. Am. Chem. Soc. 95 , 6267 (1973)]. Such states are termed pseudodegenerate states. A method is described to forecast and another to remedy such situations. The method emphasizes the relation between VB (resonance) and MO theories using graph-theoretical concepts.     

Chemical trees minimizing energy and Hosoya index

The energy of a molecular graph is a popular parameter that is defined as the sum of the absolute values of a graph’s eigenvalues. It is well known that the energy is related to the matching polynomial and thus also to the Hosoya index via a certain Coulson integral. It is quite a natural problem to minimize the energy of trees with bounded maximum degree—clearly, the case of maximum degree 4 (so-called chemical trees) is the most important one. We will show that the trees with given maximum degree that minimize the energy are the same that have been shown previously to minimize the Hosoya index and maximize the Merrifield-Simmons index, thus also proving a conjecture due to Fischermann et al. Finally, we show that the minimum energy grows linearly with the size of the trees, with explicitly computable growth constants that only depend on the maximum degree.     

Shaping the density to fit one-electron properties: Constrained RHF calculations on N2, FH,CO, and LiH

The molecular density required to give the correct values for one-electron properties is rarely given by wave functions obtained from variation methods based on the total energy or the eigenvalues. Perhaps if we knew how the density should be shaped in any particular volume to fit a particular property, the whole molecular density might then be properly described to fit the whole volume. The secant-parametrization procedure is used to constrain minimum basis set RHF wave functions for N₂, FH, CO, and LiH to determine the effects of different constraints on RHF wave functions, and to see how constraints improve the quality of small basis set RHF wave functions. One-electron property expectation values, energies, and unweighted and property weighted populations and electron density difference profiles are used to analyze the constrained wavefunctions. With the information from the constrained wave functions it should be possible to select a LCAO -CI basis and states to give the correct density for all properties. This should map onto the constrained wave function in the region of the constraint and at the same time minimize the energy of the total molecular wave function. Such a density would be suitable for the density analyses favored by Bader and Nguyen-Dang [Adv. Quantum Chem. 14 , 113 (1981)], Mezey [Theor. Chim. Acta 54 , 95 (1980); 58 , 309 (1981); 59 , 321 (1981)], and March [Theoretical Chemistry (Royal Society of Chemistry, London, 1981), Vol. 4, p. 158], and show the real atom needed to generate the molecule.