Study On The Problem Of κ-Resonance Of Some Classes Of Graphs

The concept of resonance originates from Clar's aromatic sextet theory and Randic's conjugated circuit model,κ-resonance was first investigated in benzenoid systems. A benzenoid system isκ-resonant if the resulted graph after deleting any i (0≤i≤κ) disjoint hexagons has a perfect matching. Then the research ofκ-resonance was generalized to plane graphs and 2-cell embeddings on surfaces. Let G be a plane graph or a 2-cell embedding on some surface and H a set of disjoint even faces of G. If G-H has at least one perfect matching, then H is a resonant pattern of G. A plane graph or a 2-cell embedding G on other surfaces isκ-resonant, if every i (0≤i≤κ) pairwise disjoint even faces (the "holes" are excluded) form a resonant pattern. Here a hole is either the outer face of a plane graph or an odd face or any specified one. If a graph isκ-resonant for any positive integerκ, then the graph is maximally resonant. The 1-resonance and 3-resonance of benzenoid systems, coronoid systems, open-ended nanotubes, spherical fullerene graphs, toroidal fullerene graphs and Klein-bottle fullerene graphs are well depicted but the 2-resonance for benzenoid systems, coronoid systems, open-ended nanotubes and spherical fullerene graphs has not been completely characterized. Furthermore, it was revealed that these 3-resonant graphs are maximally resonant. On the other hand, H. Zhang and F. Zhang provided the equivalence of 1-resonance and 1-extendability of plane bipartite graphs.In this thesis, we further discuss the relationship between 2-resonance and 2-extendability. As an application, we characterize theκ-resonance of boron-nitrogen fullerene graphs. Then we provide a complete characterization for theκ-resonant non-bipartite Klein-bottle fullerene graphs. Besides, we mainly study on the problem that which 3-resonant graphs are maximally resonant by investigating two classes of graphs which do possess this property.There are four chapters in the thesis. In chapter one, We first introduce some basic concepts and notations. Then we mainly introduce the background of resonance of graphs and present the research problems and their developments. At last, we outline the main results obtained in the following chapters. In the second chapter, we discuss the relationship of 2-resonance and 2-extendability. We prove that if a plane bipartite graph is 2-extendable, then it is 2-resonant. But the converse does not necessarily hold. This result cannot be generalized to the case of 3. As an application, we characterize the 2-resonance of boron-nitrogen fullerene graphs. We show that every boron-nitrogen fullerene graph is 2-resonant and then present all the 3-resonant ones. Moreover, we prove that every 3-resonant boron-nitrogen fullerene graph is maximally resonant. At the last of the chapter, we compute the cell-polynomials for all the 3-resonant boron-nitrogen fullerene graphs.In the third chapter, theκ-resonance of non-bipartite Klein-bottle fullerene graphs is characterized. We present all the 1-resonant,2-resonant andκ-resonant (κ≥3) ones, respectively. Also, every 3-resonant non-bipartite Klein-bottle fullerene graph is maximally resonant. So far, theκ-resonance of Klein-bottle fullerene graphs is completely solved.In chapter four, to further investigate the graphs which possess the property "3-resonance implies maximal resonance", we mainly consider the class of plane polygonal systems formed from a set of even rings with size more than four. This kind of graphs contains the benzenoid systems. We provide a construction method for this kind of 3-resonant graphs. Then we show that every graph constructed by this method is maximally resonant.In the fifth chapter, we consider the 3-resonance of 3-regular bipartite polyhedral graphs. The boron-nitrogen fullerene graphs are included. We characterize the 3-resonant 3-regular bipartite polyhedral graphs with cyclical edge-connectivity 3 and 4, respectively. Then we show that they are all maximally resonant. At last, we provide some examples to show that "3-resonance implies maximal resonance" does not hold for general graphs, even for plane bipartite graphs.