Maximal resonance of cubic bipartite polyhedral graphs

Let H{\mathcal{H}} be a set of disjoint faces of a cubic bipartite polyhedral graph G. If G has a perfect matching M such that the boundary of each face of H{\mathcal{H}} is an M-alternating cycle (or in other words, G-H{G-\mathcal{H}} has a perfect matching), then H{\mathcal{H}} is called a resonant pattern of G. Furthermore, G is k-resonant if every i (1 \leqslant i \leqslant k){i\,(1\,\leqslant\, i\, \leqslant\, k)} disjoint faces of G form a resonant pattern. In particular, G is called maximally resonant if G is k-resonant for all integers k \geqslant 1{k\,\geqslant\, 1}. In this paper, all the cubic bipartite polyhedral graphs, which are maximally resonant, are characterized. As a corollary, it is shown that if a cubic bipartite polyhedral graph is 3-resonant then it must be maximally resonant. However, 2-resonant ones need not to be maximally resonant.     

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.     

<Emphasis Type="Italic">k</Emphasis>-resonance in Toroidal Polyhexes*

This paper considers the k -resonance of a toroidal polyhex (or toroidal graphitoid) with a string (p, q, t) of three integers (p ≥ 2, q ≥ 2, 0 ≤ t ≤ p − 1). A toroidal polyhex G is said to be k-resonant if, for 1≤ i ≤ k, any i disjoint hexagons are mutually resonant, that is, G has a Kekulé structure (perfect matching) M such that these hexagons are M-alternating (in and off M). Characterizations for 1, 2 and 3-resonant toroidal polyhexes are given respectively in this paper. *This work is supported by FRG, Hong Kong Baptist University; NSFC and TRAPOYT.     

On k-resonance of grid graphs on the plane,torus and cylinder

Grid graphs on the plane, torus and cylinder are finite 2-connected bipartite graphs embedded on the plane, torus and cylinder, respectively, whose every interior face is bounded by a quadrangle. Let \(k\) be a positive integer, a grid graph is \(k\) -resonant if the deletion of any \(i \le k\) vertex-disjoint quadrangles from \(G\) results in a graph either having a perfect matching or being empty. If \(G\) is \(k\) -resonant for any integer \(k \ge 1\) , then it is called maximally resonant. In this study, we provide a complete characterization for the \(k\) -resonance of grid graphs \(P_m\times P_n\) on plane, \(C_m\times C_n\) on torus and \(P_m\times C_n\) on cylinder.     

k-resonant toroidal polyhexes

A toroidal polyhex H(p, q, t) is a cubic bipartite graph embedded on the torus such that each face is a hexagon, which can be described by a string (p, q, t) of three integers (p≥ 1, q≥ 1, 0≤ t≤ p−1). A set of mutually disjoint hexagons of H(p, q, t) is called a resonant pattern if H(p, q, t) has a prefect matching M such that all haxgons in are M-alternating. A toroidal polyhex H(p, q, t) is k-resonant if any i (1 ≤ i ≤ k) mutually disjoint hexagons form a resonant pattern. In [16], Shiu, Lam and Zhang characterized 1, 2 and 3-resonant toroidal polyhexes H(p, q, t) for min(p, q)≥ 2. In this paper, we characterize k-resonant toroidal polyhexes H(p, 1, t). Furthermore, we show that a toroidal polyhex H(p, q, t) is k-resonant (k≥ 3) if and only if it is 3-resonant.      

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.     

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.     

k-Resonance of Open-Ended Carbon Nanotubes

An open-ended carbon nanotube or a tubule is a part of some regular hexagonal tessellation of a cylinder. A tubule T is said to be k-resonant if for every k (or fewer) pairwise disjoint hexagons, the subgraph obtained from T by deleting all the vertices of these hexagons must have a Kekule structure (perfect matching) or must be empty. The 1-resonant tubules can be constructed by an approach provided in H. Zhang and F. Zhang, Discrete Appl. Math. 36 (1992) 291. In this paper, we give the construction method of k(k3)-resonant tubules. The lower bound of its Clar number of k(k3)-resonant tubules is also given. Note that the present paper does not consider the capped species.     

On unicyclic conjugated molecules with minimal energies

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let U(k) be the set of all unicyclic graphs with a perfect matching. Let C _g(G) be the unique cycle of G with length g(G), and M(G) be a perfect matching of G. Let U ⁰(k) be the subset of U(k) such that g(G)≡ 0 (mod 4), there are just g/2 independence edges of M(G) in C _g(G) and there are some edges of E(G)\ M(G) in G\ C _g(G) for any G∈U ⁰(k). In this paper, we discuss the graphs with minimal and second minimal energies in U ^*(k) = U(k)\ U ⁰(k), the graph with minimal energy in U ⁰(k), and propose a conjecture on the graph with minimal energy in U(k).      

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 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.     

Hosoya index of unicyclic graphs with prescribed pendent vertices

The Hosoya index z(G) of a (molecular) graph G is defined as the total number of subsets of the edge set, in which any two edges are mutually independent, i.e., the total number of independent-edge sets of G. By G(n, l, k) we denote the set of unicyclic graphs on n vertices with girth and pendent vertices being resp. l and k. Let be the graph obtained by identifying the center of the star S _n-l+1 with any vertex of C _l . By we denote the graph obtained by identifying one pendent vertex of the path P _n-l-k+1 with one pendent vertex of . In this paper, we show that is the unique unicyclic graph with minimal Hosoya index among all graphs in G(n, l, k).      

Steiner degree distance indices: Chemical applicability and bounds

The k-center Steiner degree distance ( SDD _k(G) ) has recently been introduced as a natural extension of the degree distance DD(G). In this paper, the prediction potential of SDD _k(G) is discussed. Then, the relation between this and some other well-known distance-based indices of trees is derived to explain its prediction potential. Finally, the lower and upper bounds of SDD _k(G) in terms of some other graph invariants are presented.     

The spread of unicyclic graphs with given size of maximum matchings

The spread s(G) of a graph G is defined as s(G) = max _i,j |λ _i − λ _j |, where the maximum is taken over all pairs of eigenvalues of G. Let U(n,k) denote the set of all unicyclic graphs on n vertices with a maximum matching of cardinality k, and U ^*(n,k) the set of triangle-free graphs in U(n,k). In this paper, we determine the graphs with the largest and second largest spectral radius in U ^*(n,k), and the graph with the largest spread in U(n,k).      

Elementary components of essentially disconnected polyomino graphs

An essentially disconnected polyomino graph is defined as a polyomino graph with some perfect matchings and forbidden edges. In this paper, we prove that the subgraph, obtained by deleting all the forbidden edges, is disconnected and has at least two elementary components, which generalizes the results for essentially disconnected benzenoid systems by Gutman et al. Furthermore, we show that if an essentially disconnected polyomino graph has an unit square as one of its elementary components, then it has at least three elementary components.     

Unicycle graphs with extremal Merrifield–Simmons Index

The Merrifield–Simmons index f(G) of a (molecular) graph G is defined as the number of subsets of the vertex set, in which any two vertices are non-adjacent, i.e., the number of independent-vertex sets of G. By we denote the set of unicycle graphs in which the length of its unique cycle is k. In this paper, we investigate the Merrifield–Simmons index f(G) for an unicycle graph G in . Unicycle graphs with the largest or smallest Merrifield–Simmons index are uniquely determined.     

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.     

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     

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.     

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.