Bilayered cyclofusene

Multiply-connected monolayered cyclofusene (MMC) is a fused hexacyclic system with at least two interior empty regions called holes. Multiply-connected bilayered cyclofusene (MBC) is a structure derived from an MMC by replacing each layer of hexacycles by two layers. Various properties of the equitability of these bipartite graphs are examined.     

k-coverable coronoid systems

A coronoid systemG isk-coverable if for everyk (or fewer) pairwise disjoint hexagons the subgraph, obtained fromG by deleting all thesek hexagons together with their incident edges, has at least one perfect matching. In this paper, some criteria are given to determine whether or not a given coronoid system isk-coverable.Supported by NSFC.     

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.     

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.     

On the Randić Index of Quasi-tree Graphs

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertex u and v in G. A graph G is called quasi-tree, if there exists such that G − u is a tree. In the paper, we give sharp lower and upper bounds on the Randić index of quasi-tree graphs. Mei Lu: Partially supported by NSFC (No. 10571105).     

A representation of chemical transformations by labeled graphs

A transitional labeling of a graphG is an assignment of one of the elements of the set (1, -1, 0) to each vertex and edge ofG so that each edge labeled 0 is incident only with vertices labeled 0, and no edge labeled 1 (respectively, -1) is incident with a vertex labeled -1 (respectively, 1). Chemical transformations can be represented by graphs possessing a transitional labeling. The positive (negative) graph of a transitional labelingt of a graphG is the subgraph ofG consisting of the nonnegative (nonpositive) elements ofG. The linking graph oft is the subgraph consisting of the zero elements ofG. A maximum common subgraph of two given graphsG ₁ andG ₂ is a graphF isomorphic to a common subgraph ofG ₁ andG ₂ such that the sum of the number of vertices and number of edges ofF is maximum. A transitional labelingt of a graphG is a transform if there exists an extensiont oft to a supergraphG of G such that the linking graph oft is a maximum common subgraph of the positive and negative graphs oft. Transforms are used to model chemical reaction pathways. Transforms and related concepts are studied in this paper. A characterization of transforms is also given.Dedicated to Professor Frank Harary on the occasion of his 70th birthday Research supported in part by Office of Naval Research Contract N00014-91-J-1060.     

The PI index of phenylenes

The Padmakar–Ivan (PI) index is a graph invariant defined as the summation of the sums of n _eu (e|G) and n _ev (e|G) over all the edges e = uv of a connected graph G, i.e., PI(G) = ∑ _e∈E(G)[n _eu (e|G) + n _ev (e|G)], where n _eu (e|G) is the number of edges of G lying closer to u than to v and n _ev (e|G) is the number of edges of G lying closer to v than to u. An efficient formula for calculating the PI index of phenylenes is given, and a simple relation is established between the PI index of a phenylene and of the corresponding hexagonal squeeze.     

Cyclical Edge-Connectivity of Fullerene Graphs and (k, 6)-Cages

It is shown that every fullerene graph G is cyclically 5-edge-connected, i.e., that G cannot be separated into two components, each containing a cycle, by deletion of fewer than five edges. The result is then generalized to the case of (k,6)-cages, i.e., polyhedral cubic graphs whose faces are only k-gons and hexagons. Certain linear and exponential lower bounds on the number of perfect matchings in such graphs are also established.     

PI indices of pericondensed benzenoid graphs

The Padmakar–Ivan (PI) index is a graph invariant defined as the summation of the sums of n _eu (e|G) and n _ev (e|G) over all the edges e = uv of a connected graph G, i.e., , where n _eu (e|G) is the number of edges of G lying closer to u than to v and n _ev (e|G) is the number of edges of G lying closer to v than to u. An efficient formula for calculating the PI index of a class of pericondensed benzenoid graphs consisting of three rows of hexagonal of various lengths.     

A Method of Computing the PI Index of Benzenoid Hydrocarbons Using Orthogonal Cuts

The Padmakar–Ivan (PI) index of a graph G is defined as PI , where for edge e=(u,v) are the number of edges of G lying closer to u than v, and is the number of edges of G lying closer to v than u and summation goes over all edges of G. The PI index is a Wiener–Szeged-like topological index developed very recently. In this paper, we describe a method of computing PI index of benzenoid hydrocarbons (H) using orthogonal cuts. The method requires the finding of number of edges in the orthogonal cuts in a benzenoid system (H) and the edge number of H – a task significantly simpler than the calculation of PI index directly from its definition. On the eve of 70th anniversary of both Prof. Padmakar V. Khadikar and his wife Mrs. Kusum Khadikar.     

The graph isomorphism problem

A chemically and graph-theoretically relevant problem is that of determining whether a pair of graphs G and G′ are isomorphic. A two-stage computational test is developed. In the first stage an “eigenvalue-eigenprojector” tabular graph-theoretic invariant is computed, whence if the two tables differ, G and G′ must be nonisomorphic. The second stage, utilizing the tables of the first stage, orders the vertices, thereby leading to a special labeling for them, whence if the associated adjacency matrices for G and G′ are equal, it must be that G and G′ are isomorphic. The computational implementation, and testing of the algorithm is described.     

Novel PI Indices of Hexagonal Chains

Problems don't hung on trees. Formulation of a good problem is often the most important part of a (theoretical) research. New problems usually arise when you try to solve old problems. Ivan Gutman, June 27, 1995.The Padmakar–Ivan (PI) index of hexagonal chains (i.e., the molecular graphs of unbranched catacondensed benzenoid hydrocarbons) is examined. The index PI is a graph invariant defined as the summation of the sums of edges of n _eu and n _ev over all the edges of connected graph G, where n _eu is the number of edges of G lying closer to u than to v and n _ev is the number of edges of G lying closer to v than to u. An efficient calculation of formula for PI for hexagonal chains are put forward.     

Hexagonal resonance of (3,6)-fullerenes

A (3,6)-fullerene G is a plane cubic graph whose faces are only triangles and hexagons. It follows from Euler’s formula that the number of triangles is four. A face of G is called resonant if its boundary is an alternating cycle with respect to some perfect matching of G. In this paper, we show that every hexagon of a (3,6)-fullerene G with connectivity 3 is resonant except for one graph, and there exist a pair of disjoint hexagons in G that are not mutually resonant except for two trivial graphs without disjoint hexagons. For any (3,6)-fullerene with connectivity 2, we show that it is composed of n(n ≥ 1) concentric layers of hexagons, capped on each end by a cap formed by two adjacent triangles, and none of its hexagons is resonant.     

Graphical properties of polyhexes: Perfect matching vector and forcing

From the viewpoint of graph theory and its applications, subgraphs of the tiling of the plane with unit squares have long been studied in statistical mechanics, In organic chemistry, a much more relevant case concerns subgraphs of the tiling with unit hexagons. Our purpose here is to take a mathematical view of such polyhex graphsG and study two novel concepts concerning perfect matchingsM. First, the forcing number ofM is the smallest number of edges ofM which are not contained in any other perfect matching ofG. Second, the perfect matching vector ofM is written (n ₃,n ₂,n ₁,n ₀), wheren _k is the number of hexagons with exactlyk edges inM. We establish some initial results involving these two concepts and pose some questions.     

A note on the cyclical edge-connectivity of fullerene graphs

A fullerene graph is a 3-regular (cubic) and 3-connected spherical graph that has exactly 12 pentagonal faces and other hexagonal faces. The cyclical edge-connectivity of a graph G is the maximum integer k such that G cannot be separated into two components, each containing a cycle, by deletion of fewer than k edges. Došlić proved that the cyclical edge-connectivity of every fullerene graph is equal to 5. By using Euler’s formula, we give a simplified proof, mending a small oversight in Došlić’s proof. Further, it is proved that the cyclical connectivity of every fullerene graph is also equal to 5.     

Global Forcing Number of Benzenoid Graphs

A global forcing set in a simple connected graph G with a perfect matching is any subset S of E(G) such that the restriction of the characteristic function of perfect matchings of G on S is an injection. The number of edges in a global forcing set of the smallest cardinality is called the global forcing number of G. In this paper we prove several results concerning global forcing sets and numbers of benzenoid graphs. In particular, we prove that all catacondensed benzenoids and catafused coronoids with n hexagons have the global forcing number equal to n, and that for pericondensed benzenoids the global forcing number is always strictly smaller than the number of hexagons.     

On the Randić Index of Acyclic Conjugated Molecules

The Randić index of an organic molecule whose molecular graph is G is the sum of the weights (d(u)d(v))^−1/2 of all edges uv of G, where d(u) and d(v) are the degrees of the vertices u and v in G. We give a sharp lower bound on the Randić index of conjugated trees (trees with a perfect matching) in terms of the number of vertices. A sharp lower bound on the Randić index of trees with a given size of matching is also given Mei Lu: Partially supported by NNSFC (No. 60172005) Lian-zhu Zhang: Partially supported by NNSFC (No. 10271105) Feng Tian: Partially supported by NNSFC (No. 10431020)     

Polymer gels and brushes at surfaces

We discuss the adsorption of polymer gels on flat surfaces. Even in cases of complete wetting, where the spreading power S is positive and where an equivalent liquid would spread, the elastic stresses due to the gel deformation upon adsorption oppose spreading. The competition between elasticity characterized by the bulk shear modulus G and capillarity, characterized by the spreading power S, defines a typical length scale 1 = S/G for the deformation in the gel. Macroscopic gels larger than 1 deform only at their edges over a region of size 1. Microscopic gels show a finite deformation despite the elastic stresses. These results can be compared to confined polymer brushes.     

The Overall Hyper-Wiener Index

The concept of overall connectivity of a graph G was extended here to the definition of the overall hyper-Wiener index OWW(G) of a graph G, defined as the sum of the hyper-Wiener indexes in all subgraphs of G, as well as the sum of eth-order terms, ^e OWW(G), with e being the number of edges in the subgraph. The potential usefulness of the overall hyper-Wiener index in QSAR/QSPR is evaluated by its correlation with a number of properties of C3-C8 alkanes and cycloalkanes.     

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.