Properties Of Paths And Cycles In Strong-[s,t]-Graphs And Quasi-claw-free Graphs In The Condition Of H-local Connect Further

The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active.What is more,paths and cycles are effective tools to analyze graphs.Many many practical problems can be attributed to the problem of paths and cycles.In fact,the famous Hamilton problem belongs to the problem of paths and cycles.There are a lot of research work on this issue were made by many scholars at home and abroad.The research results and progress can be found in literature. After the development for dozens of years,the contents in properties of graphs’path and cycle become more and more rich and specific.The properties of path include Hamilton path (traceability),homogeneous-traceability, longest path, Hamilton-connected,pan-connectivity, path extensibility and so on; the properties of cycle include Hamilton cycle, Dominating-cycle, longest cycle, (vertex-)pancyclicity, cycle extendsibility vertex-disjoint cycle,cycle-covered and soHowever, it is usually very difficult to study Hamilton problem in those graphs without any restriction. So we turn to explore the special graphs,such as the graphs not containing some forbidden subgraphs. The claw graph is one more represen-tative class.The first motivation for studying properties of claw-free graphs appar- ently appeared from two papers of Beineke’s characterization of line graphs.They were published in 1968 and 1970.After that,many people pay attention to the claw-free graphs, The research of claw-free graph was very active in late 70s and early 80s.Some famous results about claw-free graphs can be seen in[4] and [33] .In addition, the definition of claw-free graph has been extended to several larger graph families in different views, such as quasi-claw-free graphs,almost claw-free graphs,etG.Because it is.difficult to extend many good results of claw-free graphs to almost claw-free graphs.Therefore, TengYanyan and Haiyan Liu gave the definition of strongly almost claw-free graphs:quasi-claw-free graph-,which contain the fam-ily of claw-free graphs and is contained in the family of almost claw-free graphs.We can call quasi-claw-free graphs,almost claw-free graphs,quasi-claw-free graphs sim-ilar claw-free graphs.Some new forbidden subgraphs are also defined continuously recently.In 2005,Liu Chunfang defined a new graph family-[s,t]-graphs in,that is,there are at least t edges in every included subgraphs of s vertices in graph G.According to this graph,Chengjianmin defined a new graph family-strong-[s,t]-graphs in, that is,there are at least t independent edges in every included subgraphs of s vertices in graph G.The[s,t]-graphs can be used in traffic network,communications,the config-uration of computer networks because of it’s edges even distribution.Some famous results can be seen in and about [s,t]-graphs.When we research paths and circles of graphs,connectivity and quasi-connect are commonly used.In 1989, Cunqun Zhang gave the definition of quasi-locally con-nected graphs, after that he studied the properties of claw-free graphs and quasi-claw-free graphs in the condition of quasi-locally connected graphs.In 2002 Tengyan yan and Haiyan You defined almost-locally connected graphs.In 2004,the triangu-larly connected graphs was given by Hongjian Lai,he also gave many good results of claw-free graphs under this condition.In 2008,Mingyan Liu gave the definition of H-local connected graphs on the basic of research on many different graphs.In this paper, we mainly discuss the properties of graph’s paths and circles in strong-[s,t] graphs and quasi-claw-free graphs in the condition of H-local connect further.In the first chapter, we give a brief introduction about the basic concepts, terminologies and symbols which will be used in this paper. In the meantime, we also give some related research backgrounds and some known results.In the second chapter, we mainly study the properties of paths and cycles in strong-[s,t] graphs and give the following results:Theorem 2.1.1 If G is a strong [k+3,2] and have no Hamilton cycle, C is one of the longest cycle in G, any branch of G-V(C) suppose H meet|Nc(H)|≥k, then G is isomorphic to (k+1)K2∨Gk.(Gk is an arbitrary graph of order k).Corollary 2.1.1 If G is a k-connected strong[k+3,2] graph with δ≥(k+ 1)and have no Hamilton path, then G has a Hamilton cycle or G is isomorphic to (k+1)K2 V Gk-(Gk is an arbitrary graph of order k)Theorem 2.2.1 If G is a strong[k+4,2] and have no Hamilton path, P is one of the longest path in G, any branch of G-V(P) suppose H meet|Np(H)|> k, then G is isomorphic to (k+2)K2∨Gk.(Gk is an arbitrary graph of order k).Corollary 2.2.1 If G is a k-connected strong[k+4,2] graph with δ≥ (k+1), then G has a Hamilton path or G is isomorphic to (k+2)K2∨Gk.(Gk is an arbitrary graph of order k).Theorem 2.3.1 If G is a k-connected strong[k+2,3] graph with δ> (k+1), then G is Hamilton connectivity or G is isomorphic to (k)K2∨Gk-(Gk is an arbitrary graph of order k).Corollary 2.3.1 If G is a k-connected strong[k+2,2] graph with δ≥(k+1), then G is Hamilton connectivity or G is isomorphic to (k)K2∨Gk.(Gk is an arbitrary graph of order k).In the third chapter, we mainly study the path extendable of strong-[5,2] and give the following results:Theorem 3.1.2 If G is a-2-connected and local connected strong-graph, then G is path extendable.In the forth chapter, we mainly study the properties of 1-2 extend in P3-locally connected quasi-claw-free graphs, and give the following results:Theorem 4.1 If G is a connected,P3-locally connected quasi-claw-free graph, then G is 1-2 extendable.Corollary 4.1 If G is a connected,P3-locally connected claw-free graph, then G is 1-2 extendable...