Forbidden Subgraph And Hamilton Problem Of Graphs

Hamilton problem is one of fundamental problems in graph theory.The following aspects are mainly focused on:cycle problem and path problem.In detail,there are many problems of hamilton cycle,pancyclicity, vertex pancyclicity,cycle extensibility,hamilton-connected,longest path, longest cycle etc.But usually it is diffcult to work out the hamilton problem of any graph,then we turn to explore the graphs not containing forbidden subgraph,for example ,claw-free graph,almost claw-free graph,quasi claw-free graph.While in this paper,a new class of graphs is definded.It is called (K1,9;q)-graph.We mainly discuss the related hamilton problem of (K1,4;2)-graphs which contain claw-free graphs.In the first chapter ,we give a brief introduction about the basic concepts, terminologies and symbols which are used in this paper and research Vmckground with some known results.In the second chapter,we prove an important result of (K1,p;q)-graph,that is: Theorem 2.1 Every (K1,p;q)-graph is a (K1,p+1;q+1)-graph. Corollary 2.2 Let t ≥ 1 be an integer.Then every (K1,p; q)-graph is a (K1,p+1; q+t)-graph.In the third chapter,we introduce the concepts of k-closure and some results about it. For claw-free graph G,clk{G) is well-definded and keep many properties of hamiltonicity. Let (?) be a class of graph.We say that the class (?) is stable under the closure (or simply stable) if clk(G) ∈ (?) for every G ∈ (?).Let (?) be a stable class and let ξ be a property.We say that the property ξ is stable under the closure(or simply stable) in the class (?) if G ∈ (?) has ξ if and only if clk{G) has ξ.For m-connected claw-free graph,Ryjacek etal. defined the concepts of closure and proved the following theorem:Theorem 3.1.M Let G be a claw-free graph.Then (1) the closure cl{G) is well-defined; (2) c(G) = c(cl{G)).Corollary 3.2[4] Let G be a claw-free graph.Then G is hamiltonian if and only if cl(G) is hamiltonian.Theorem 3.3[5] Let G be a claw-free graph.Then p(G) = p(cl(G)).Corollary 3.4[5] Let G be a claw-free graph.Then G is traceable if and only if cl(G) is traceable.Theorem 3.5[5] For any n ≥ 14,there is a 2-connected claw-free graph on n vertices such that cl(G) is homogenously traceable,while G is not homogenously traceable.Theorem 3.6[5] For every m ≥ 2,there exists a m-connected claw-free graph G such that cl(G) is pancyclic,while G is not paracyclic.Theorem 3.7[5] For every m ≥ 2,there exists a m-connected claw-free graph G such that cl(G) is vertex pancydic,while G is not vertex pancyclic.Theorem 3.8[5] For every m ≥ 2,there exists a m-connected claw-free graph G such that cl(G) is cycle extendable,while G is not cycle extendable.We know that the circumference and the length of the longest path are stable properties. For m-connected claw-free graphs,the properties of pancyclicity, vertex pancyclicity and cycle extensibility are not stable for any m.For claw-free graph, harniltonian-connected and homogenously traceable are also not stable.In 1998,Bollobas etal. defined a new closure clk{G)(k ≥ 1) as a generalization of cl(G) and proved the following theorem.Theorem 3.9[6] Let G be a claw-free graph.Then(1) clk(G) is uniquely determined for each k,(2) G is hamiltonian-connected if and only if cl3(G) is hamiltonian-connected,and(3) G is homogenously traceable if and only if cl2(G) is homogenously traceable. Hence hamiltonian-connected and homogenously traceable are stable in cl3(G)and cl2(G) espectively.In the third chapter,we main study stable properties of (K1,4;2)-graph.Since (K1,4; 2)-graph contains claw-free graph,the unstable properties of claw-free graph are also unstable to (K1,4;2)-graph.So we only work out stable properties of [K1,4; 2)-graph.In this chapter,there are four sections.In the first section,we prove theorem 3.10 and theorem 3.11.Theorem 3.10 Let G be a (K1,4;2)-graph. If G is a T3-free or K1 ∨ P4-free graph, cl(G) is still a (K1,4; 2)-graph.Theorem 3.11 Let G be a (K1,4; 2)-graph. If G is a T3-free or K1∨ P4-free graph,cl(G) is well-definded.In the second section ,we prove theorem 3.12 and give infinitely many (K1,4;2)-graphs G such that cl(G) is hamiltonian while G is not hamiltonian, which illustratesthat the condition 'T3-free or K1 ∨ P4- free ' in theorem 3.11 can not be deleted.We also give infinitely many graphs which satisfy the condition in theorem 3.12 while do not in theorem 3.1.Theorem 3.12 Let G be a (K1,4; 2)-graph. If G is a T3-free or K1∨ P4-free graph,c(G) = c(cl(G)).Corollary 3.13 Let G be a (K1,4;2)-graph. If G is a T3-free or K1∨ P4-free graph,G is hamiltonian if and only if cl(G) is hamiltonian.In the third section,we prove theorem 3.14 and give infinitely many (K1,4; 2)-graphs G such that cl(G) is traceable while G is not traceable, which illustrates that the condition ' T3- free or K1∨ P4-free ' in theorem 3.14 can not be deleted.We also give infinitely many graphs which satisfy the condition in theorem 3.14 while do not in theorem 3.3.Theorem 3.14 Let G be a (K1,4;2)-graph. If G is a T3- free or K1∨ P4-freegraph.p(G)=p(cl(G)).Corollary 3.15 Let G be a (K1,4;2)-graph. If G is a T3-free or K1∨ P4-free graph,G is traceable if and only if cl(G) is traceable.In the fourth section we prove theorem 3.16.We also give infinitely many graphs which satisfy the condition in theorem 3.16 while do not in theorem 3.9.Theorem 3.16 Let G be a (K1,4; 2)-graph. If G is a {T3, K1∨ P5}-free or K1∨P4-free graph, G is hamiltonian-connected if and only if cl3(G) is harniltonian-connected.In the fourth chapter,we study the hamiltonicity of connected,N2-locally connected and (K1,4; 2)-graph. We prove theorem 4.2.We also give a graph which satisfies the condition in theorem 4.2 while does not in theorem 4.1.Theorem 4.1[7] Let G be a connected,N2-locally connected claw-free graph without vertices of degree 1,which does not contain an induced subgraph H isomorphic G1 or G2 such that N(v) of every vertex v of degree 4 in H is disconnected.Then G is hamiltonian.Theorem 4.2 It is shown that let G be a connected,N2-locally connected (K1,4; 2)-graph with δ > 6,which does not contain an induced subgraph H isomorphic to one of G1,G2 and G3,then G is hamiltonian.