Hamiltonicity Of (K_1,4;2)-graphs

The problem on hamiltonicity of graphs is a very important problem in graph theory and the research is very active. There are a lot of papers dealing with this problem each year. Recently.researches on hamiltonicity has been on in some special fields. Hamiltonicity of claw-free graph is an important research field, To-day,there are a number of results on this topic. The research on hamiltonicity and the new advance can be refered to [2]-[8]. The research on hamiltonicity of claw-free graph can be refered to [9]-[10]. There are many advance results on traceabil-ity,pancyclic,cycle extensibility.hamiltonian connectedness, the concept of claw-free graph has also been extended to almost claw-free graph and quasi claw-free graph. In this paper.we extend claw-free graph to (K_1,4;2)-graph,and obtain several new theorems which are the improvements and generalizations of some known results on this topic. The circumference of graph i.e. the length of longest cycle is an important, parameter in graph. Investigating longest cycle of graph can often promote the study of hamiltonian problem. In paticular,if the length of longest cycle is the order of graph,then the graph is hamiltonian. In the second part we will consider the problem of longest cycle in (K_1,4;2)-graph and quasi claw-free graph.The first chapter of this paper gives a brief introduction about the basic concepts, terminologies and symboles which are used in this paper and research background with some known results. In second chapter,we discuss the trace-ability of 2-connected (K_1,4;2)-graphs; In third chapter,we consider k-connected (K_1,4;2)-graphs, and present a sufficient condition of hamiltionicity about square graphs with some important corollaries; In forth chapter,we get some results about shortest walk of (K_1,4;2)-graphs; In fifth chapter,we discuss the longest, cycle of 2-connected (K_1,4;2)-graphs; In the last chapter,we discuss the longest cycle of 2-connected quasi claw-free graphs.The main results of this paper are the following.Theorem 2.1.2 Let, G be a 2-connected (A'M; 2)-graph with \G\ = n, and NC > ^ .then G is traceable.Theorem 3.1.5 Let G be a fc-connected (A'M; 2)-graph, if rv(G2) < fc,then G is hamiltonian.From Theorem 3.1.5,we can get some important corollaries,they are generalizations of some known results about claw-free graphs.Corollary 3.3.1 Let G be a fc-connected (ft"M;2)-graph {k > 2), D{X) ^ 0 is true for any independent set X with k + 1 vertices,then G is hamiltonian.Corollary 3.3.2 Let G be a ^-connected (A'M; 2)-graph {k > 2), if j(G) < fc.then G is hamiltonian.Corollary 3.3.3 Let G be a ^-connected (ArM; 2)-graph [k > 2),G is hamiltonian ifZuexd{v) >n-kis true for any independent set X with k + 1 vertices.Corollary 3.3.4 Let G be a A;-connected (A'M; 2)-graph(fc > 2),\vhen the diameter of G at most 2, then G is hamiltonian.Theorem 4.1.5 Let G be a fc-eonnected (A',.4;2)-graph with \G\ = ?>:then(1) G have a 2-walk.(2) for any x e V(G') there is a 2-walk C such that v(xX') = 1 if and only if x is not a cutvertex of G.(3) If {N(x)) is connected then there is a shortest 2-walk C such that r(.r, C) = 1.Theorem 5.1.4 Let G be a 2-connected (A\,,; 2)-graph with \G\ = n,when ^ > 3, G has a cycle with the length at, least, mm{n,26 + 2}.Theorem 6.1.3 Let G be a 2-connected quasi claw-free graph with \G\ = n. G ha,s a cycle with the length at least min{n, 2(5 + 4}.