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.     

Fullerene Graphs with Exponentially Many Perfect Matchings

We show that for all sufficiently large even p there is a fullerene graph on p vertices that has exponentially many perfect matchings in terms of the number of vertices. Further, we show that all fullerenes with full icosahedral symmetry group have exponentially many perfect matchings and indicate how such results could be extended to the fullerenes with lower symmetry.     

A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs

An essentially disconnected generalized polyomino graph is defined as a generalized polyomino graph with some perfect matchings and forbidden edges. The number of perfect matchings of a generalized polyomino graph G is the product of the number of perfect matchings of each elementary component in G. In this paper, we obtain a lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs.     

On lower bounds of number of perfect matchings in fullerene graphs

Couting perfect matchings in graphs is a very difficult problem. Some recently developed decomposition techniques allowed us to estimate the lower bound of the number of perfect matchings in certain classes of graphs. By applying these techniques, it will be shown that every fullerene graph with p vertices contains at least p/2+1 perfect matchings. It is a significant improvement over a previously published estimate, which claimed at least three perfect matchings in every fullerene graph. As an interesting chemical consequence, it is noted that every bisubstituted derivative of a fullerene still permits a Kekulé structure.     

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.     

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.     

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.     

Unicyclic Hückel molecular graphs with minimal energy

The minimal energy of unicyclic Hückel molecular graphs with Kekulé structures, i.e., unicyclic graphs with perfect matchings, of which all vertices have degrees less than four in graph theory, is investigated. The set of these graphs is denoted by such that for any graph in , n is the number of vertices of the graph and l the number of vertices of the cycle contained in the graph. For a given n(n ≥ 6), the graphs with minimal energy of have been discussed. MSC 2000: 05C17, 05C35     

Counterexamples to a proposed algorithm for Fries structures of benzenoids

The Fries number of a benzenoid is the maximum number of benzenoid hexagons over all of its Kekulé structures (perfect matchings), and a Fries canonical structure is a perfect matching that realises this maximum. A recently published algorithm claims to determine Fries canonical structures of benzenoids via iterated Hadamard products based on the adjacency matrix (Ciesielski et?al. in Symmetry 2:1390–1400, 2010). This algorithm is re-examined here. Convergence is typically rapid and often yields a single candidate perfect matching, but the algorithm can give an exponential number of choices, of which only a small number are canonical. More worryingly, the algorithm is found to give incorrect results for the Fries number for some benzenoids with as few as seven hexagonal faces. We give a combinatorial reformulation of the algorithm in terms of linear combinations of perfect matchings (with weights at each stage proportional to the products of weights of the edges included in a matching). In all the cases we have examined, the algorithm converges to a maximum-weight matching (or combination of maximum-weight matchings), and where the algorithm fails, either no best Fries matching is of maximum weight, or a best Fries matching is of maximum weight but a sub-optimal matching of the same weight is chosen.     

Leapfrog fullerenes have many perfect matchings

A leapfrog fullerene on p vertices contains at least 2 ^p/8 different perfect matchings.     

Connections between Wiener index and matchings

Let T be an acyclic molecule with n vertices, and let S(T) be the acyclic molecule obtained from T by replacing each edge of T by a path of length two. In this work, we show that the Wiener index of T can be explained as the number of matchings with n−2 edges in S(T). Furthermore, some related results are also obtained MSC: 05C12 Weigen Yan: This work is supported by FMSTF (2004J024) and NSFF(E0540007) Yeong-Nan Yeh: Partially supported by NSC94-2115-M001-017     

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.     

Fusenes and benzenoids with perfect matchings

In this paper, a method to constructively enumerate fusenes and benzenoids with perfect matchings is given. It is based on an algorithm for generating all fusenes and benzenoids and introduces new restrictions into the generation process that avoid the generation of structures without perfect matchings.      

Pfaffian polyominos on the Klein bottle

If a graph G is Pfaffian, then the number of perfect matchings of G can be computed in polynomial time. So it makes sense to test whether a graph is Pfaffian. Historically in organic chemistry and combinatorial mathematics, polyominos have attracted the most attention. In this paper, we characterize all Pfaffian polyominos on the Klein bottle.     

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.     

The Gutman Formulas for Algebraic Structure Count

The concept of ASC (algebraic structure count) is introduced into theoretical organic chemistry by Wilcox as the difference between the number of so-called even and odd Kekulé structures of a conjugated molecule. Precisely, algebraic structure count (ASC-value) of the bipartite graph G corresponding to the skeleton of a conjugated hydrocarbon is defined by where A is the adjacency matrix of G. In the case of bipartite planar graphs containing only circuits of the length of the form 4s+2 (s=1,2,...) (the case of benzenoid hydrocarbons), this number is equal to the number of the perfect matchings (K-value) of G. However, if some of circuits are of the length 4s (s=1,2,...) then the problem of evaluation ASC-value becomes more complicated. The theorem formulated and proved in this paper gives a simple and efficient algorithm for calculation of algebraic structure count of an arbitrary bipartite graphs with n+n vertices. Three recurrence formulas for the algebraic structure count – the Gutman formulas, which are closely analogous to the well-known recurrence formula K{G}=K{G–e}+K{G–(e)} for the number of perfect matchings (G–e is the subgraph obtained from the graph G by deleting the edge e and G–(e) is the subgraph obtained from G by deleting both the edge e and its terminal vertices) are obtained as a simple corollary of the theorem.     

On maximal resonance of polyomino graphs

A polyomino graph is a finite plane 2-connected bipartite graph every interior face of which is bounded by a regular square of side length one. Let k be a positive integer, a polyomino graph G is k-resonant if the deletion of any i ≤ k vertex-disjoint squares from G results in a graph either having perfect matchings or being empty. If graph G is k-resonant for any integer k ≥ 1, then it is called maximally resonant. All maximally resonant polyomino graphs are characterized in this work. As a result, the least integer k such that a k-resonant polyomino graph is maximally resonant is determined.     

Electrical field effects on dipole moment, structure and energetic of (H2O)n (2 n 15) cluster

The effect of an external electric field on water clusters of the (H₂O)_n type, with [1 n 15], in the ground state was analyzed at the B3LYP/cc-pVTZ level of theory. The calculations showed that an external electric field changes the number of hydrogen bonds, reduces the cluster sizes and increases the strength of the inter-cluster hydrogen bonds. The particular symmetry of the cluster and the null dipole moment in these specific configurations suggest that their stability can be associated with a perfect alignment of the water molecules, maximizing attractive electrostatic interactions caused by changes in the charge distribution of the clusters.     

Kekulé structures of hexagonal chains—some unusual connections

It is known since 1977 that the number K of Kekulé structures of a hexagonal chain is equal to the topological Z-index of a pertinently constructed “caterpillar” tree. Based on this relation we now connect K with some of other, seemingly unrelated, concepts: continuants (from number theory) and matchings of the path–graph (further related to Fibonacci numbers). We also arrive at a tridiagonal determinantal expression for K.     

Finding more perfect matchings in leapfrog fullerenes

We use some recent results on the existence of long cycles in leapfrog fullerenes to establish new exponential lower bounds on the number of perfect matchings in such graphs. The new bounds are expressed in terms of Fibonacci numbers.