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.     

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.     

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.     

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

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.     

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

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

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.     

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

Multiplicative degree-Kirchhoff index and number of spanning trees of a zigzag polyhex nanotube TUHC[2n, 2]

Let L_n denote the linear hexagonal chain containing n hexagons. Then identifying the opposite lateral edges of L_n in ordered way yields TUHC[2n, 2] , the zigzag polyhex nanotube, whereas identifying those of L_n in reversed way yields M_n, the hexagonal Möbius chain. In this article, we first obtain the explicit formulae of the multiplicative degree-Kirchhoff index, the Kemeny's invariant, the total number of spanning trees of TUHC[2n, 2] , respectively. Then we show that the multiplicative degree-Kirchhoff index of TUHC[2n, 2] is approximately one-third of its Gutman index. Based on these obtained results we can at last get the corresponding results for M_n.     

Packing in honeycomb networks

Molecules arranging themselves into predictable patterns on silicon chips could lead to microprocessors with much smaller circuit elements. Mathematically, assembling in predictable patterns is equivalent to packing in graphs. An H-packing of a graph G is a set of vertex disjoint subgraphs of G, each of which is isomorphic to a fixed graph H. If H is the complete graph K ₂, the maximum H-packing problem becomes the familiar maximum matching problem. In this paper we give algorithms to find a perfect packing of HC(n) with P ₆ and K _1,3 when n is even and thus determines their packing numbers. Further we also study the packing of HC(n) with 1, 3-dimethyl cyclohexane.     

New upper bounds on Zagreb indices

The first Zagreb index M ₁(G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M ₂(G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper we obtain an upper bound on the first Zagreb index M ₁(G) of G in terms of the number of vertices (n), number of edges (m), maximum vertex degree (Δ₁), second maximum vertex degree (Δ₂) and minimum vertex degree (δ). Using this result we find an upper bound on M ₂(G). Moreover, we present upper bounds on and in terms of n,  m, Δ₁, Δ₂, δ, where denotes the complement of G.     

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.     

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.     

Sharp Bounds for the Second Zagreb Index of Unicyclic Graphs

The second Zagreb index M ₂(G) of a (molecule) 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. In this paper, we give sharp upper and lower bounds on the second Zagreb index of unicyclic graphs with n vertices and k pendant vertices. From which, and C _n have the maximum and minimum the second Zagreb index among all unicyclic graphs with n vertices, respectively.     

Spectral moments of polymer graphs

Summary It is shown that for anyk, thekth spectral moment of a polymer graph composed ofn monomer units is an exact linear function of the parametern. This linear relation holds for all values ofn, greater than a critical value ₀=₀(k).on leave from Faculty of Science, University of Kragujevac     

On the Ordering of a Class of Graphs with Respect to their Matching Numbers

Based on the number of k-matching m(G,k) of a graph G, Gutman and Zhang introduced an order relation of graphs: for graphs G ₁ and G ₂, if m(G ₁,k) ≥ m(G ₂,k) for all k. The order relation has important applications in comparing Hosaya indices and energies of molecular graphs and has been widely studied. Especially, Gutman and Zhang gave complete orders of six classes of graphs with respect to the relation . In this paper, we consider a class of graphs with special structure, which is a generalization of a class of graphs studied by Gutman and Zhang. Some order relations in the class of graphs are given, and the maximum and minimum elements with respect to the order relation are determined. The new results can be applied to order some classes of graphs by their matching numbers.     

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.