| I. Chemical graph theory is a branch of mathematical chemistry that is concerned with topological indices and topological properties of chemical molecule graphs as well as the relations between the chemical molecules' phsicochemical properties and their topological indices and topological properties. Chemical graph theory plays an important role in predicting and synthesizing new chemical compounds and new medicines.In the topological theory of benzenoid hydrocarbons, a hexagonal system (or benzenoid system) denotes the carbon atom skeleton graph of a benzenoid hydrocarbon, that is a 2-connected plane graph whose every interior face is bounded by a regular hexagon. A Kekule struc-ture K of a hexagonal system H is also a perfect matching (1-factor) of H. A cycle (or circuit) C in H is said to be conjugated or resonant if there is a Kekule structure K of H such that C is a K-alternating cycle. In the conjugated circuits model [2-25], conjugated circuits with different sizes have different resonant energies. On the other hand, from a purely empirical standpoint, Chemists found that various electronic properties of hexagonal systems can be predicted by appropriately defining a set of mutually resonant hexagons with the maximum cardinal number, [26-36] where a set of mutually resonant hexagons means a set of disjoint hexagons for which there is a Kekule structure K so that all of the the disjoint hexagons are K-alternating hexagons. An interesting problem is under which conditions any k disjoint hexagons of a hexagonal system H are mutually resonant? If a hexagonal system H satisfies such property, that is, for a positive integer k and 1 < t < k, any t disjoint hexagons of H are mutually resonant, it is said to be k-resonant or k-coverable.The concept of cover was originally introduced by Gutman [37].111-coverable hexagonal systems were first investigated by Fuji Zhang and Rongsi Chen [38]. Some necessary and sufficient conditions for a hexagonal systems to be l-resonant were established. Maolin Zheng [39] further gave some pretty results for fc-resonant hexagonal systems with k > 2. Some fair necessary and sufficient conditions for a hexagonal systems to be k-resonant were given.As a generalization of k-coverable hexagonal systems, Quo Xiaofeng and Fuji Zhang [1] introduced k-cycle resonant graphs. Some properties of fc-cycle resonant graphs and some necessary and sufficient conditions for a graph to be fc-cycle resonant were given. Guo Xiaofeng and Fuji Zhang [40] further investigated general planar k-cycle resonant graphs with k = 1,2. Some new necessary and sufficient conditions for a graph to be planar 1-cycle resonant graphs or planar 2-cycle resonant graphs were given. Zhixia Xu and Xiaofeng Guo [41] investigated the construction and the recognition of planar 1-cycle resonant graphs, and established a linear algorithm for deciding if a planar graph is planar 1-cycle resonant.In chapter 1, we investigate the construction of planar 2-cycle resonant graphs, in the light of the necessary and sufficient conditions for a graph to be 2-cycle resonant graphs. A recursive method for constructing any planar 2-cycle resonant graph from smaller planar 2-cycle resonant graphs and simple planar 1-cycle resonant graphs is given. In chapter 2, we further investigate the structure of planar 2-cycle resonant graphs, and establish a linear algorithm for recognizing planar 2-cycle resonant graphs.II. A problem, which has attracted much attention in graph theory and is not yet completely settled, is the following: Given a graph G with perfect matchings, to calculate the number of perfect matching of G. In fact, Valiant [57] proved the problem is TVP-hard - even when G is bipartite. Motivated by studies of this problem, considerable effort has been devoted to developing a canonical decomposition theory for graph with perfect matchings. Call a edgeinof graph G allowed if it lies in some perfect matching of it, forbidden if it lies in no perfect matching of it. A graph is elementary if its allowed edges...
|
PDF Full Text Request