Cyclical Edge-connectivity, Resonance And Hamiltonicity Of Fullerene Graphs On Surfaces

The Fullerene graphs on surfaces are finite 3-regular graphs embedded on surfaces with faces bounded by only cycles of length 5 or 6.Only four surfaces are possible for such embedding:the sphere,the torus,the Klein bottle and the projective plane.The number of pentagonal faces of Fullerene graphs on the four surfaces is 12,0,0 and 6, respectively.The usual Fullerene graphs are the spherical Fullerene graphs,that is,the molecular graphs of all-carbon Fullerenes.Theoretical research on matching-related problems in Fullerene graphs has been done extensively.This thesis is divided into four chapters to discuss Fullerene graphs on surfaces.We determine the cyclical edge-connectivities of Fullerene graphs on the torus,the Klein bottle and the projective plane,respectively.Then using the above obtained results on the cyclical edge-connectivity,we show that in Fullerene graphs on the sphere and the projective plane as well as in some non-bipartite Fullerene graphs on the Klein bottle,every hexagon is resonant.Furthermore we discuss the k-resonance of spherical Fullerene graphs and indicate that a spherical Fullerene graph is 3-resonant if and only if it is k(k≥3)-resonant.Finally,we show that spherical Fullerene graphs with nondegenerate cyclical 6-edge cuts are hamiltonian.Chapter 1 gives an overview of the applications and research progresses on spherical Fullerene graphs,proposes the main problems to be discussed and surveys the main results obtained in this thesis.In Chapter 2,the cyclical edge-connectivities of Fullerene graphs on surfaces are discussed.A graph G is said to be cyclically k-edge connected,if there exists no edgecut X with less than k edges in G,such that there are at least two components of G-X each containing a cycle.The maximum integer k such that G is cyclically kedge connected is called the cyclical edge-connectivity of G.In 2003,T.Do(?)li(?)proved that the cyclical edge-connectivity of spherical Fullerene graphs is 5.Using the result that Fullerene graphs are cyclically 4-edge connected,H.Zhang and F.Zhang proved that spherical Fullerene graphs are 2-extendable and furthermore,a best general lower bound on the number of perfect matchings of these graphs is given.In this chapter, first we show that the cyclical edge-connectivity of any 3-regular graph is equal to its cyclical connectivity.Then we give a simplified proof of the T.Do(?)li(?)'s result in the above.Finally we obtain the cyclical edge-connectivities of Fullerene graphs on the other three surfaces,especially we point out that the cyclical edge-connectivity of any Fullerene graph on the projective plane is also 5.In Chapter 3,the k-resonance of Fullerene graphs on surfaces are discussed. First of all,we give a general result:for a cyclically 4-edge connected 3-regular graph G with at least one cycle of length 6,by deleting any cycle of length 6 the resulting subgraph either has a perfect matching or is bipartite.Using this result and the cyclical edge-connectivity of Fullerene graphs on surfaces,we show that in Fullerene graphs on the sphere,the projective plane and in non-bipartite Fullerene graphs K_o(k,q)(k≥4,q≥2)on the Klein bottle every hexagon is resonant,i.e., any hexagon is alternating with respect to some perfect matching.A Fullerene graph G on surfaces is called k-resonant if any at most k pairwise disjoint hexagons in G are all alternating with respect to some perfect matching of G.As the k-resonance of Fullerene graphs,on the torus and bipartite Fullerene graphs on the Klein bottle have been completely characterized,we focus mainly on the k-resonance of spherical Fullerene graphs.Firstly,we prove that every Leapfrog Fullerene graph is 2-resonant. In addition,we show that there are infinite Fullerene graphs-which are not 2-resonant by constructing some counterexamples:nanotubes of arbitrary length with two special caps as subgraphs.Secondly,we completely characterize the k(k≥3)-resonant spherical Fullerene graphs and show that there are only nine 3-resonant spherical Fullerene graphs.By constructing thesenine Fullerene graphs,we point out that they are also k(k＞3)-resonant which indicates that any spherical Fullerene graph is 3-resonant if and only if it is k(k≥3)-resonant.Finally,we discuss the Hamiltonicity of Fullerene graphs in Chapter 4.In 1969 Barnette conjectured that 3-regular 3-connected plane graphs with faces bounded by cycles of length at most 6 are hamiltonian.So far even for spherical Fullerene graphs, Barnette's Conjecture is not completely resolved.In this Chapter we show that this conjecture is true for spherical Fullerene graphs with non-degenerate cyclical 6-edge cut.