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.     

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

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.     

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.     

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     

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.      

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.     

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.     

On the connectivity index of trees

The connectivity index χ₁(G) of a graph G is the sum of the weights d(u)d(v) of all edges uv of G, where d(u) denotes the degree of the vertex u. Let T(n, r) be the set of trees on n vertices with diameter r. In this paper, we determine all trees in T(n, r) with the largest and the second largest connectivity index. Also, the trees in T(n, r) with the largest and the second largest connectivity index are characterized. Mei Lu is partially supported by NNSFC (No. 10571105).     

An Upper Bound for the Clar Number of Fullerene Graphs

A fullerene graph is a three-regular and three-connected plane graph exactly 12 faces of which are pentagons and the remaining faces are hexagons. Let F _n be a fullerene graph with n vertices. The Clar number c(F _n ) of F _n is the maximum size of sextet patterns, the sets of disjoint hexagons which are all M-alternating for a perfect matching (or Kekulé structure) M of F _n . A sharp upper bound of Clar number for any fullerene graphs is obtained in this article: . Two famous members of fullerenes C₆₀ (Buckministerfullerene) and C₇₀ achieve this upper bound. There exist infinitely many fullerene graphs achieving this upper bound among zigzag and armchair carbon nanotubes.     

The Merrifield–Simmons index in (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">n</Emphasis> + 1)-graphs

A (n, n + 1)-graph G is a connected simple graph with n vertices and n + 1 edges. In this paper, we determine the upper bound for the Merrifield–Simmons index in (n, n + 1)–graphs in terms of the order n, and characterize the (n, n + 1)–graph with the largest Merrifield–Simmons index.     

On bicyclic graphs 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 G(n) be the class of bicyclic graphs G on n vertices and containing no disjoint odd cycles of lengths k and l with k + l 2 (mod 4). In this paper, the graphs in G(n) with minimal, second-minimal and third-minimal energies are determined.AMS subject classification: 05C50, 05C35     

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.     

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.     

Extremal (<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">n</Emphasis> + 1)-graphs with respected to zeroth- order general Randić index

A (n, n + 1)-graph G is a connected simple graph with n vertices and n + 1 edges. If d _v denotes the degree of the vertex v, then the zeroth-order general Randić index of the graph G is defined as , where α is a real number. We characterize, for any α, the (n,n + 1)-graphs with the smallest and greatest zeroth-order general Randić index.     

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

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.     

On the Randić Index

The Randić index of an organic molecule whose molecular graph G is defined as the sum of (d(u)d(v))^−1/2 over all pairs of adjacent vertices of G, where d(u) is the degree of the vertex u in G. In Delorme et al., Discrete Math. 257 (2002) 29, Delorme et al gave a best-possible lower bound on the Randić index of a triangle-free graph G with given minimum degree δ(G). In the paper, we first point out a mistake in the proof of their result (Theorem 2 of Delorme et al., Discrete Math. 257 (2002) 29), and then we will show that the result holds when δ(G)≥ 2.     

On Unicycle Graphs with Maximum and Minimum Zeroth-order Genenal Randić Index

Let G be a graph and d _v denote the degree of the vertex v in G. The zeroth-order general Randić index of a graph is defined as R _α⁰(G) = ∑ _v∈V(G) d _v ^α where α is an arbitrary real number. In this paper, we obtained the lower and upper bounds for the zeroth-order general Randić index R _α⁰(G) among all unicycle graphs G of order n. We give a clear picture for R _α⁰(G) of unicycle graphs according to real number α in different intervals.