Computer generation of matching polynimials of chemical graphs and lattices

A computer program in Pascal is developed for computing the matching polynomials of graphs and lattices. This program is based on the recursive relation for matching polynomials outlined by Hosoya [Bull. Chem. Soc. Jpn., 44 , 2332 (1971)], Gutman and Hosoya [Theor. Chim. Acta, 48 , 279 (1978)], and others. The graph whose matching polynomial is of interest is reduced recursively until the graph reduces to several trees. The characteristic polynomial of a tree is the same as the matching polynomial. The characteristic polynomials of resulting trees are computed using the computer program based on Frame's method developed by Balasubramanian [Theor. Chim. Acta, 65 , 49 (1984)]; J. Comput. Chem., 5 , 387 (1984). The resulting polynomials are then assembled to compute the matching polynomial of the initial graph. The program is especially useful in generating the matching polynomials of graphs containing a large number of vertices. The matching polynomials thus generated are potentially useful in several applications such as lattice statistics (dimer covering problem), aromaticity, valence bond methods (enumeration of perfect matchings) in the calculation of grand canonical partition functions, in the computation of thermodynamic properties of saturated hydrocarbons, and in chemical documentation.     

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.     

Normal Components, Kekulé Patterns, and Clar Patterns in Plane Bipartite Graphs

As a general case of molecular graphs of polycyclic alternant hydrocarbons, we consider a plane bipartite graph G with a Kekulé pattern (perfect matching). An edge of G is called nonfixed if it belongs to some, but not all, perfect matchings of G. Several criteria in terms of resonant cells for determining whether G is elementary (i.e., without fixed edges) are reviewed. By applying perfect matching theory developed in plane bipartite graphs, in a unified and simpler way we study the decomposition of plane bipartite graphs with fixed edges into normal components, which is shown useful for resonance theory, in particular, cell and sextet polynomials. Further correspondence between the Kekulé patterns and Clar (resonant) patterns are revealed.     

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.     

The complexity of the Clar number problem and an exact algorithm

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441–448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is \(\mathsf {NP}\)-hard. We also prove \(\mathsf {NP}\)-hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes.     

On the Randić Index of Unicyclic Conjugated Molecules

The Randić index R(G) of a graph G is the sum of the weights of all edges uv of G, where d(u) denotes the degree of the vertex u. In this paper, we first present a sharp lower bound on the Randić index of conjugated unicyclic graphs (unicyclic graphs with perfect matching). Also a sharp lower bound on the Randić index of unicyclic graphs is given in terms of the order and given size of matching.     

On the Ordering of a Class of Graphs with Respect to their Matching Numbers

Based on the number of k-matching m(G,k) of a graph G, Gutman and Zhang introduced an order relation of graphs: for graphs G ₁ and G ₂, if m(G ₁,k) ≥ m(G ₂,k) for all k. The order relation has important applications in comparing Hosaya indices and energies of molecular graphs and has been widely studied. Especially, Gutman and Zhang gave complete orders of six classes of graphs with respect to the relation . In this paper, we consider a class of graphs with special structure, which is a generalization of a class of graphs studied by Gutman and Zhang. Some order relations in the class of graphs are given, and the maximum and minimum elements with respect to the order relation are determined. The new results can be applied to order some classes of graphs by their matching numbers.     

Operator technique for obtaining the recursion formulas of characteristic and matching polynomials as applied to polyhex graphs

A simple and efficient method, called an operator technique, for obtaining the recurrence relation of a given counting polynomial, e.g., characteristic P_G(x) or matching M_G(x) polynomial, for periodic networks is proposed. By using this technique the recurrence relations of the P_G(x) and M_G(x) polynomials for the linear zigzag-type and kinked polyacene graphs were obtained. For the lower members of these series of graphs, the coefficients of P_G(x) and M_G(x) polynomials are tabulated.     

A comparison between 1-factor count and resonant pattern count in plane non-bipartite graphs

The concept of resonant (or Clar) pattern is extended to a plane non-bipartite graph G in this paper: a set of disjoint interior faces of G is called a resonant pattern if such face boundaries are all M-conjugated cycles for some 1-factor (Kekulé structure or perfect matching) M of G. In particular, a resonant pattern of benzenoids and fullerenes coincides with a sextet pattern. By applying a novel approach, the principle of inclusion and exclusion in combinatorics, we show that for any plane graphs, 1-factor count is not less than the resonant pattern count, which generalize the corresponding results in benzenoid systems and plane bipartite graphs. Applications to fullerenes are also discussed.AMS Subject classification: 05C70, 05C90, 92E10     

On the z-counting polynomial for edge-weighted graphs

The construction of the Z-counting polynomial for edge-weighted graphs is discussed.Dedicated to Professor Haruo Hosoya (Tokyo) on the occasion of his 55th birthday for enriching chemical graph theory with the elegant concept of the Z-counting polynomial.     

On the ordering of benzenoid chains and cyclo-polyphenacenes with respect to their numbers of Clar aromatic sextets

Based on Clar aromatic sextet theory [Clar, The Aromatic Serxtet (Wiley, New York, 1972)] and the concept of sextet polynomial introduced by Hosoya and Yamaguchi [Mathematical Concepts in Organic Chemistry (Springer, Berlin, 1986)], we define a new ordering of benzenoid systems. For two isomeric benzenoid systems B₁ and B₂, we say B₁>B₂ if each coefficient of sextet polynomial of B₁ is no less than the corresponding coefficient of sextet polynomial of B₂. In this paper, we consider the ordering of the benzenoid chains. The maximal and second maximal benzenoid chains as well as the minimal, the second minimal up to the fourth minimal benzenoid chains are determined. Furthermore, under this ordering, we determine the maximal and second maximal cyclo-polyphenacenes as well as the minimal, the second minimal, and up to the seventh minimal cyclo-polyphenacenes.     

Higher-order Fibonacci numbers

We consider a generalization of Fibonacci numbers that was motivated by the relationship of the HosoyaZ topological index to the Fibonacci numbers. In the case of the linear chain structures the new higher order Fibonacci numbers ^h F _n are directly related to the higher order Hosoya-typeZ numbers. We investigate the limitsF _n /F _n–1 and the corresponding equations, the roots of which allow one to write a general expression for^hF_n. We also report on the ^h F counting polynomials that give the partition of the ^h F numbers in contributions arising fromk pairs of disjoint paths of lengthh. It is interesting to see that the partitions of ^h F are hidden in the Pascal triangle in a similar way to the partitions of the Fibonacci numbers that were discovered some time ago by Hoggatt. We end with illustrations of the recursion formulas for the higher order Hosoya numbers for several families of graphs that are based on the corresponding recursions for the higher Fibonacci numbers.Dedicated to Professor Haruo Hosoya of Ochanomizu University, Tokyo, Japan, on the occasion of 25 years of the topological index Z.     

Graphs corresponding to reference polynomial or to circuit characteristic polynomial

A vertex-weighted graphG ^* is studied which is obtained by deleting edgee _rs in a circuit of a graphG and giving two vertices _r and _s weightsh _r = 1 andh _s = -1, respectively. It is shown that if subgraphG - _r is identical with subgraphG - _s, then the reference polynomial ofG ^* is identical with that ofG and the characteristic polynomial ofG ^* contains the contributions due to only a certain part of the circuits found in the original graphG. This result gives a simple way to find a graph whose characteristic polynomial is equal to the reference polynomial in the topological resonance energy theory or to the circuit characteristic polynomial in the circuit resonance energy theory. This approach can be applied not only to Hilckel graphs but also to Möbius graphs, provided that they satisfy a certain condition. The significances of this new type of reference graph thus obtained are pointed out.     

Generalized Wheland polynomial for large graphs

We report the generalized Wheland polynomial for acyclic graphs depicting polyenes havingn = 10 carbon atoms. We consider the problem of deriving generalized Wheland polynomials for larger chains by recursion. The recursion Wh(n + l;x) =, Wh(n; x) + (1 –x)Wh(n – 1;x) allows one to find the next larger generalized Wheland polynomial for a chain having an even number of vertices by knowing generalized Wheland polynomials of chains having fewer vertices. The recursion, however, does not allow one to predict the generalized Wheland polynomial for a chain having an odd number of vertices from smaller chains! Here we report a procedure which allows one to derive the generalized Wheland polynomial for a chain having an odd number of vertices. This is achieved by combining the coefficients for rings having the same number of vertices. The generalized Wheland polynomials for odd rings are simply related to the generalized Wheland polynomials for smaller chains and can be derived from the information on smaller chains. This makes it possible to extend the recursion for generalized Wheland polynomials for arbitrarily largen.     

Chemical applications of topology and group theory. 26. The sextuple diamond-square-diamond rearrangement of the icosahedron through a cuboctahedron intermediate

The details of the symmetry factoring of the graphs corresponding to the icosahedron and the cuboctahedron are presented. Such symmetry factoring procedures use the sequence of two-foldC ₂ and threefoldC ₃ elementsC ₂ xC ₂ x CZ x C3 to give disconnected graphs having eigenvalue spectra similar to those of the original polyhedra but with components having only one and two vertices. In addition, the same symmetry factoring sequence is used to determine the eigenvalue spectrum of an intermediate in the sextuple diamond-square process for conversion of the icosahedron to the cuboctahedron.This paper is dedicated to Professor Frank Harary in recognition of his pioneering work in areas of graph theory closely related to chemical problems. For part 25 of this series, see ref. [1].     

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.     

On Extremal Unicyclic Molecular Graphs with Prescribed Girth and Minimal Hosoya Index

Let G be an n-vertex unicyclic molecular graph and Z(G) be its Hosoya index, let F _n be the nth Fibonacci number. It is proved in this paper that if G has girth l then Z(G) ≥ F _l+1+(n−l)F _l +F _l-1, with the equality holding if and only if G is isomorphic to , the unicyclic graph obtained by pasting the unique non-1-valent vertex of the complete bipartite graph K _1,n-l to a vertex of an l-vertex cycle C _l . A direct consequence of this observation is that the minimum Hosoya index of n-vertex unicyclic graphs is 2n−2 and the unique extremal unicyclic graph is. The second minimal Hosoya index and the corresponding extremal unicyclic graphs are also determined.     

k-resonant benzenoid systems and k-cycle resonant graphs.

A benzenoid system (or hexagonal system) H is said to be k-resonant if, for 1 < or = t < or = k, any t disjoint hexagons of H are mutually resonant; that is, there is a Kekule structure (or perfect matching) K of H such that each of the k hexagons is an K-alternating hexagon. A connected graph G is said to be k-cycle resonant if, for 1 < or = t < or = k, any t disjoint cycles in G are mutually resonant. The concept of k-resonant benzenoid systems is closely related to Clar's aromatic sextet theory, and the concept of k-cycle resonant graphs is a natural generalization of k-resonant benzenoid systems. Some necessary and sufficient conditions for a benzenoid system (respectively a graph) to be k-resonant (respectively k-cycle resonant) have been established. In this paper, we will give a survey on investigations of k-resonant benzenoid systems and k-cycle resonant graphs.     

Graph-theoretical analysis of the clar's aromatic sextet : Mathematical properties of the set of the kekulé patterns and the sextet polynomial for polycyclic aromatic hydrocarbons

The mathematical structure of a set of the Kekulé patterns for a polycyclic aromatic hydrocarbon has been analysed graph-theoretically. By defining the proper and improper sextets, sextet pattern, Clar transformation, and sextet rotation, one can prove the important property of the sextet polynomial B_G(x) as B_G(1) = K(G), where K(G) is the number of the Kekulé patterns for thin polyhex graph G. For fat polyhex graphs such as coronene the above relation is found to be also valid by introducing the concept of a super sextet. All the Kekule patterns for a given G are shown to form a hierarchical tree structure by the sextet rotation. The theory developed in this paper gives a mathematical basis and interpretation for the concept of the Clar's aromatic sextet.