Connection, H-Locally Connection And Some Properties Of Paths And Cycles In "s,1"-Graphs

As an important branch of modern mathematics,the graph theory has been ap-plied more and more widely in the electrical network,information transmission, urbanplanning and so on.In the nature and the human society, a lot of things and relation-ships can be described as graphs. Paths and cycles are two basic structures of graphs.In fact, many practical problems can be attributed to the problem of paths and cycles.Therefore, the research about them is very active. Some famous results about this canbe seen in [1]-[4]. What is more, the famous Hamilton problem is about paths andcycles of graph in essence. After the development for dozens of years, the contents inproperties of graphs'path and cycle become more and more rich and specific. Theproperties of path include Hamilton path (traceability), longest path, panconnectivity,path extendsibility and so on; the properties of cycle include Hamilton cycle, longestcycle, (vertex-)pancyclicity, vertex-disjoint cycle, cycle extendsibility and so on.However, we can not deny the fact that it is usually very di?cult 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 appeared fromBeineke's characterization of line graphs in [5]-[6]. However, the main impulse thatturned the attention of the graph theory community to the class of claw-free graphswas given in late 70s and early 80s. Some famous results about claw-free graphs canbe seen in [7]-[32]. In addition, the definition of claw-free graph has been extended to3 several larger graph families in di?erent views, such as quasi-claw-free graphs, almostclaw-free graphs, (K1,4;2)-graphs, DCT graphs etc.Some famous results about this canbe seen in [33]-[46]. Liu Chunfang [47] defined a new graph family–[s,t]-graphs, thatis, there are at least t edges in every included subgraphs of s vertices in graph G. [s,t]-graphs can be used in tra?c network, communications, the configuration of computernetworks, etc. Some results about properties of paths and cycles in [[s, t]-graphs canbe seen in [47]-[50].Connection and locally connection are commen conditions in discussing the prop-erties of graphs'paths and cycles.In 1989,CunQuan Zhang gave the definition of quasi-locally connected graphs.After that he studied the properties of claw-free graphs inthe condition of quasi-locally connection. In the latter years we gave many relateddefinions such as almost locally connected, triangularly connected,2-order neighborconnected and so on. In 2008,MingYing Liu[51] gave the definition of H-locally con-nected graphs.After that, she studied the paths and cycles of claw-free graphs andquasi-claw-free graphs in the condition of K2?locally connection.In this paper, wemainly discuss the properties of paths and cycles in [s, 1]-graphs which are importantpart of [s, t]-graphs in the condition of H-locally connection.In the first chapter, we give a brief introduction about the basic concepts, termi-nologies and symbols which will be used in this paper. In the meantime, we also givesome related research backgrounds and some known results.In the second chapter, we mainly study the Hamilton cycles of [4,1]-graphs inthe condition of di?erent connections and give the following results:Theorem 2.4 The su?cient and necessary condition of a 2-connected [4,1]-graphto be a Hamiltonian is that it is not isomorphic to three kinds of specific graphs.Corollary 2.6 The connected,K2-locally connected [4,1]-graph has a Hamiltoncycle.In the third chapter, we mainly study the cycle extendence of [4,1]-graphs andgive the following result: Theorem 3.4 The connected,P3-locally connected [4,1]-graph is 1-2 cycle ex-tendable.Moreover,the result is best possible.Corollary 3.5 If G is a connected,P3-locally connected [4,1]-graph withδ(G)≥4,then G is fully 1-2 cycle extendable.In the fourth chapter, we mainly study the path extendence of [4,2]-graphs andgive the following result:Theorem 4.4 If G is a connected,K2-locally connected [4,2]-graph,then any pathP satisfying 6≤|P | < |V (G)| of G is extendable.Moreover,the result is best possible.Theorem 4.5 If G is a connected,locally connected [4,2]-graph,then any path Psatisfying 6≤|P | < |V (G)| of G is extendable.Moreover,the result is best possible.