| The hamiltonian problem is an important research topic in structural graph theory. It is well known that the problem is closely related to Four Color Problem. So it is concerned by many graph theorists. The problem of deciding whether a given graph has a hamiltonian cycle or not is XP-hard by the issue of computa-tional complexity. Therefore, the research of hamiltonian problem is concentrated on sufficient conditions implying a graph to be hamiltonian.The known sufficient conditions with respect to hamiltonian graphs mainly include two important types. The first one is based on the numerical conditions, such as minimum degree, degree sum, independence number and neighborhood union; the second one is the subgraph structure, forbidding some specific subgraph, i.e., forbidden subgraph conditions. For a family H of connected graphs, a graph G is called H-free if G does not contain H as an induced subgraph for any H E H, and we call each H a forbidden subgraph. K1,3is also called claw, which is one of the most frequently used as forbidden subgraph. Note that K1,3-free graph means claw-free graph. In1984, Matthews and Sumner proposed a famous conjecture that every4-connected claw-free graph is hamiltonian. Towards this conjecture, more and more graph theorists concentrate on the research of hamiltonicity of claw-free graphs, and many interesting concepts, methods and techniques have been presented.In this thesis, we concentrate on the study of forbidden subgraph pairs for hamiltonicity in3-connected graphs. According to a result of Chen, Egawa, Gould and Saito, every forbidden subgraph pair implying hamiltonicity in3-connected graphs must contain K1,3or K1,4.Firstly, we consider K1,3as one forbidden subgraph. For integer i>3, let Pi be a path with exactly i vertices. Let i,j, k be non-negative integers with i+j+k≥1, the graph Ni,j,k is obtained by identifying end vertices of three disjoint paths of lengths i, j, k to the vertices of a triangle. Luczak and Pfender proved that every3-connected{K1,3,P11}-free graph is hamiltonian; Lai, Xiong, Yan and Yan proved that every3-connected{K1,3,N8,0,0}-free graph is hamiltonian. In this thesis, we show that every3-connectcd{K1,3,Ni,j,k}-free graph is hamiltonian, where i, j, k are any positive integers satisfying i+j+k=9. The number9in the conclusion is best possible, i.e. it cannot be replaced by a larger number. In chapter two, we propose some key lemmas and the main idea of proofs. Given to the symmetry, there are seven kinds of combinations for any positive integers i, j, k satisfying i+j+k=9. So, we divide the seven results into three groups. In chapter three, we prove that every3-connccted{k1,3,N5,2,2}-free or{K1,3,N4,3,2}-free graph is hamiltonian. In chapter four, we prove that every3-connected{K1,3,Y}-free graph is hamiltonian, where Y is one of N7,1,1, N6,2,1,N5,3,1and N4,4,1. In chapter five, we prove that every3-connected{K1,3, N3,3,3}-free graph is hamiltonian.Secondly, we consider K1,4as one forbidden subgraph. We show that every3-connected{K1,4, P5}-free graph is hamiltonian. Furthermore, we fully characterize all pairs of forbidden subgraphs with one being K1,4:Let H be connected graphs on at least three vertices, every3-connected{K1,4, H}-free graph is hamiltonian if and only if H is one of P3, P4and P5. This result extends the related work of Chen, Egawa, Gould and Saito.
|
PDF Full Text Request