Paths And Cycles In Several H-locally Connected Graphs

Paths and cycles are two basic structures of graphs. Many practical problemscan be attributed to the problem of paths and cycles. Therefore, The problem onpaths and cycles of graphs is a very importantproblem in graph theory and theresearch is also active. What is more, the famous Hamilton problem belongs to theproblem of paths and cycles of graphs in essence. Many scholars at home and abroadmade a lot of research work on this issue. The research results and progress in thisarea can be found in literature[38]-[42]. The condition of degree and neighborhoodunions becomes an important way to study the problems. In this respect, a lotof outstanding achievements have be made. After the development for dozens ofyears, the contents in properties of graphs’path and cycle become more and morerich and specific. The properties of path include Hamilton path （traceability）,longest path, panconnectivity, path extendsibility and so on; the properties of cycleinclude Hamilton cycle, longest cycle, （vertex-）pancyclicity, vertex-disjoint cycle,cycle extendsibility and so on.However, we can not deny the fact that it is usually very difcult to studyHamilton problem in those graphs without any restriction. Then we turn to explorethe graphs not containing some forbidden subgraphs such as claw-free graphs. Thefirst motivation for studying properties of claw-free graphs apparently appearedfrom Beineke’s characterization of line graphs in [17]. However, the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s. Some famous results about claw-free graphs can be seen in [1]-[3],[19]-[31]. In addition, the definition of claw-freegraph has been extended to several larger graph families in diferent views, suchas quasi-claw-free graphs, almost claw-free graphs, (K_1,4;2)-graphs etc. In 2005,Liu Chunfang [4] defined a new graph family—[s,t]-graphs, that is, there are atleast t edges in every included subgraphs of s vertices in graph G. According tothis graph,Cheng Jianmin defined a new graph family—strong-[s,t] graphs [51],that is, there are at least t independent edges in every included subgraphs of svertices in graph G. [s,t]- graphs can be used in trafc network, communications,the configuration of computer networks, etc.Some famous results about [s,t]- graphs can be seen in [8] [10]. Connectivityand quasi-connect are commonly used terms when we reseach paths and cycles ofgraphs.In 1989,CunQuan Zhang gave the definition of quasi-connected graps. Af-ter that he studied the properties of claw-free graphs and quasi-claw-free graphsin the conditions of quasi-locally connected. In the latter years many related de-fination such as almost locally connect, the triangularly connect, 2-order neighborconnectand so on. In 2008, Mingying Liu gave the definition of H-local connectedgraphs and gave some basic reseach on K₂-locally connected claw-free graphs. Inthis chapter, we reseach the claw-free graphs,(K_1,4; 2) graphs, [5,3]-graphs in thecondition of H-local connect furtherly.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, wealso give some related research backgrounds and some known results.In the second chapter, we mainly study the shortest paths in K3-locally con-nected (K_1,4; 2) graphs and the property of hamilton in K₂-locally connected (K_1,4; 2)-graphs. we give the following results:Theorem 2.1 Let G be a connected, K3-locally connected (K_1,4; 2) graphs, and for G[{x, y, z}]∈G, the length of the shortest path between any two diferentvetexes in G[N （xyz）]≤11.Corollary 2.2 Let G be a connected,K2-locally connected (K_1,4; 2) graphs,and for xy∈E（G）. P = x₁x₂...xkis the shortest path between any two diferentvetexes, then k≤8.Theorem 2.3 Let G be a connected, K₂-locally connected (K_1,4; 2) graphsand |G|≥5, then G is hamilton.In the third chapter, we mainly study the the property of 1-2 extend in P₃-locally connected claw-free graphs and give the following result:Theorem 3.1 Let G be a connected, P₃-locally connected claw-free graph,then G is 1-2 extendable.In the fourth chapter, we mainly study the the property of cycle extend inP₃-locally connected [5,3]-graphs and give the following result:Theorem 4.1 Let G be a connected, P₃-locally connected [5,3]-graph and|G|≥8, then G is 1-2 extendable.Theorem 4.1 Let G be a connected, P₃-locally connected [5,3]-graph and|G|≥10, then G is pancyclic.