Factorization and recursion relations of the matching and characteristic polynomials of periodic polymer networks

Recent developments in the analysis of mathematical structure of the matching and characteristic polynomials of linear and cyclic periodic polymer networks are surveyed, especially on the newly found efficient algorithms and techniques for deriving their recursion relations and factorization expressions. Advantages and disadvantages of these two polynomials for manipulating large networks are compared and discussed with examples. Contrary to the case of singly connected polymer networks, only a few useful mathematical properties are shown to be found for doubly connected polymer networks. Linear and cyclic fence graphs are proposed to be defined instead of the conventional definitions of the so-called Hückel and Möbius ladder graphs, so that simpler and more useful mathematical relations hold for their matching polynomials.     

DNA Computing of Bipartite Graphs for Maximum Matching

Let M be a matching in a graph G. It is defined that an M-augmenting path must obtain one element of M. In this paper, it is obtained that a matching M in a graph G is a maximum matching if and only if G contains no M-augmenting path and M is a maximal matching in G. It supplies a theoretical basis to DNA computing. A detailed discussion is given of DNA algorithms for the solutions of the maximal matching problem and maximum matching one in a bipartite graph.     

Critical evaluation of search algorithms for automated molecular docking and database screening

The DOCK program explores possible orientations of a molecule within a macromolecular active site by superimposing atoms onto precomputed site points. Here we compare a number of different search methods, including an exhaustive matching algorithm based on a single docking graph. We evaluate the performance of each method by screening a small database of molecules to a variety of macromolecular targets. By varying the amount of sampling, we can monitor the time convergence of scores and rankings. We not only show that the site point–directed search is tenfold faster than a random search, but that the single graph matching algorithm boosts the speed of database screening up to 60-fold. The new algorithm, in fact, outperforms the bipartite graph matching algorithm currently used in DOCK. The results indicate that a critical issue for rapid database screening is the extent to which a search method biases run time toward the highest-ranking molecules. The single docking graph matching algorithm will be incorporated into DOCK version 4.0. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1175–1189     

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.     

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.     

Intrinsic chirality of triple‐layered naphthalenophane and related graphs

We prove that the graph of triplelayered naphthalenophane and an infinite class of related graphs are all intrinsically chiral. We also give examples to illustrate that not all graphs which are contractible to a Möbius ladder with three rungs are necessarily intrinsically chiral.     

Analysis of the relationship among the graphs isomorphic to multilayered cyclic fence graphs (MLCFG)

Multilayered cyclic fence graphs (MLCFG, E(m,n), F(m,n), D(m,n), G(m,n), X(m,n)) are proposed to be defined, all of which are composed of m 2n-membered cycles with periodic bridging. They are also cubic and bipartite. Hamiltonian wheel graph, H (n,[j(k)]), and parallelogram-shaped polyhex graph are also defined. All the members of MLCFGs are found to be isomorphic to the so-called "torus benzenoid graphs", while some members of MLCFGs are found to be related to the Hamilton wheel graphs. Through the construction of Hamilton wheel graph and the matrix representation by Kirby, a number of isomorphic relations among MLCFGs, Hamilton wheel graphs, and polyhex graphs were obtained. These relations among the MLCFG members were found also by the help of the characteristic quantities of MLCFGs.     

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.     

Double Bonds in Fused Hexacyclic Systems

If a hexacyclic graph, G, represents a benzenoid, a perfect matching corresponds to the location of double bonds (pi-bonds). We present an algorithm for counting the number of configurations of double bonds for various benzenoids.     

基于图论的色谱指纹图谱谱峰的全局匹配

以色谱工作站的积分数据为基础,定义了允许匹配峰组的域,提出了在域内根据色谱峰面积、保留时间计算各匹配峰组之间距离矩阵的公式,从而形成有向图。采用图论中的最短路径算法寻找可能的匹配峰组中的最佳匹配峰组。采用优化的匹配参数,对珍菊降压片、丹参提取物、柴胡皂苷提取物、人参皂苷提取物的HPLC谱图进行匹配并将有关结果与国家药典委员会推出的指纹图谱软件自动匹配结果作了比较。结果表明:本算法可最大程度地匹配可能的色谱峰并极少出现错配、漏配峰组,无需手动校正。     

Saturation number of fullerene graphs

Saturation number of a graph G is the minimum possible size of a maximal matching in G. We establish improved upper and lower bounds on the saturation number in fullerene graphs and discuss their sharpness and quality.     

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.     

Characterization of Supramolecular Hidden Chirality of Hydrogen‐Bonded Networks by Advanced Graph Set Analysis

Supramolecular hidden chirality of hydrogen‐bonded (HB) networks of primary ammonium carboxylates was exposed by advanced graph set analysis from a symmetric viewpoint in topology. The ring‐type HB (R‐HB) networks are topologically regarded as faces, and therefore exhibit prochirality and positional isomerism due to substituents attached on the faces. To describe the symmetric properties of the faces, additional symbols, Re (right‐handed or clockwise), Si (left‐handed or anticlockwise), and m (mirror), were proposed. According to the symbols, various kinds of faces were classified based on the symmetry. This symmetry consideration of the faces enables us to precisely evaluate supramolecular chirality, especially its handedness, of 0D‐cubic, 1D‐ladder and 2D‐sheet HB networks that are composed of the faces. The 1D‐ladder and 2D‐sheet HB networks generate chirality by accumulating the chiral faces in 1D and 2D manners, respectively, whereas 0D‐cubic HB networks generate chirality based on combinations of eight kinds of faces, similar to the chirality of dice.     

Scalable distance similarity of chemical structures

Screening a library of molecular graphs for an exact or approximate match with one particular molecular graph, the query graph, is reduced to list comparisons. The lists contain lengths of shortest paths in graph Voronoi regions. This induces the notion of shortest path similarity. All graphs that are shortest path similar to the query graph are efficiently retrievable. The same applies to approximate or similarity matching. For the retrieval of all superstructures of a query, shortest path lists are modified to distance patterns. This also allows algorithmic support for query construction.     

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     

On bicriticality of (3,6)-fullerene graphs

A (3,6)-fullerene is a plane cubic graph whose faces are only triangles and hexagons. A connected graph G with at least \(2n+2\) vertices is said to be n-extendable if it has n independent edges and every set of n independent edges extends to a perfect matching of G. A graph G is said to be bicritical if for every pair of distinct vertices u and v, \(G-u-v\) has a perfect matching. It is known that every (3,6)-fullerene is 1-extendable, but not 2-extendable. In this short paper, we show that a (3,6)-fullerene G is bicritical if and only if G has the connectivity 3 and is not isomorphic to one graph (2,4,2). As a surprising consequence we have that a (3,6)-fullerene is bicritical if and only if each hexagonal face is resonant.     

Resonance structure counts in parallelogram-like benzenoids with holes

If a hexacyclic graph G represents a benzenoid, a perfect matching corresponds to a configuration of π-bonds. We present an algorithm for counting the number of configurations of π-bonds for parallelogram-like benzenoids with parallelogram-like holes by counting descending paths in a corresponding rectangular mesh with rectangular holes.     

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.     

三梯级和四梯级圆筒和Mbius分子的拓扑特性研究

Walba等以其卓越的工作,合成了三-THYME(C_(42)H_(72)O_(18))和四-THYME(C_(56)H_(96)O_(24))圆筒及其Mbius扭曲环带分子,被誉为拓扑学进入有机化学领域的奇迹,成为迄今为止拓扑立体化学研究的重要内容,但从拓扑学的观点探索分子图拓扑结构特性尚缺乏深入研究,本文作者考虑到一般性,曾将扭曲数T为偶数(0,2,4)的定义为Hckel型,扭曲数     

New Lower Bound on the Number of Perfect Matchings in Fullerene Graphs

A fullerene graph is a cubic and 3-connected plane graph (or spherical map) that has exactly 12 faces of size 5 and other faces of size 6, which can be regarded as the molecular graph of a fullerene. T. Doli [3] obtained that a fullerene graph with p vertices has at least (p+2)/2 perfect matchings by applying the recently developed decomposition techniques in matching theory of graphs. This note gets a better lower bound 3(p+2)/4 of the number of perfect matchings of a fullerene graph by finding its 2-extendability. This property further implies a chemical consequence that every derivative of a fullerene by substituting any two pairs of adjacent carbon atoms permits a Kekulé structure.