The Cycles In 2-connected [4, 2]-graphs And The Fully Cycle Extensibility Of Graphs With High Connectivity

The problem on hamiltonicity of graphs is a very important problem ingraph theory and the research is very active. There are a lot of papersdealing with this problem each year. In 1857, Irish mathematician Hamiltonput forward a problem:"what is the necessary and sufficient condition whena connected graph has a Hamilton cycle.". However, it has not been solveduntil now. Later people found that it is a NPC problem, so they began tostudy the problem in indirect ways.At the same time, based on Hamiltonproblem, a research on natures of cycles in graph has been carried out.These natures are hamiltonicity, pancyclicity, extensibility etc. As weall know, the fully cycle extensibility of graphs is more powerful thanthe pancyclicity of graphs, the pancyclicity of graphs is more powerfulthan the hamiltonicity of graphs. Therefore, to study the pancyclicity andthe fully cycle extensibility is to study the hamiltonicity of graphs. Theresearch on hamiltonicity and the new advance can be refered to [17]-[23].The research on pancyclicity and the new advance can be refered to [24]-[34].The research on fully cycle extensibility and the new advance can be referedto [4]-[15].The study about these natures mainly focuses on two aspects:one aspect is to study the sufficient condition of these natures, and theother is to study these natures on some special graphs.The thesis is mainly about the problem on the cycle natures of twospecial families of graphs, one family of graphs is [ s ,t]-graph,ChunfangLiu put forward the concept of [ s ,t]-graph at first and began to researchit, the research of [ s ,t]-graph has profound applicant value,a tipicalapplication is on the network of computer. The other family of graphs isgraph with high connectivity. The high connectivity means that theconnectivity of graph is high in comparision with the order of graph. Whenthe connectivity of graph is high enough, the graph can possess all kindsof cycle natures. What will happen to the cycle natures of graph with thedropping of the connectivity of graph?The fully cycle extensibility ofgraphs with high connectivity has been discussed in the thesis. In orderto discuss the problem more easily , I put forward the concept ofs -vertices connected graph, that is,the graph with connectivity ofG ? s+1.Based on this ,I mainly discuss the fully cycle extensibility of5-vertices connected graphs and 6-vertices connected graphs,that is,thefully cycle extensibility of graphs with high connectivity whoseconnectivity is G ?4 and G ?5 respectively.Based on these results Iput forward a conjecture on the fully cycle extensibility of s-verticesconnected graphs (the graphs whose connectivity is G ? s+1).At the endof the third chapter, examples are given to illustrate the restriction tothe order of graph in the Theorems and conjectures is sharp.This thesis is divided into three chapters.In the first chapter, wegive a brief introduction about the basic concepts, terminologies andsymboles which are used in this thesis and research background with someknown results;In the second chapter, we discuss the cycle in 2-connected[ 4,2]-graphs;In the third chapter ,we discuss the fully cycle extensibilityof graph with high connectivity and put forward a conjecture.The main results of this thesis go as the following.Theorem2.1.1 Let G be a 2-connected [ 4,2]-graph,C is a cycle inG which satisfies the condition V (C )< V(G) , then G has a cyclewhich perimeter is C +1 or G isomorphics with K 2,3, K 1,1,3,F1 , F2 , F3 , F4 , F5 .( F1 , F2 , F3 , F4 , F5 go as the following)图 F1 图 F2 图 F3图 F4 图 F5Corollary 3.1.1 Let G be a 4-vertices connected graph with G ≥9,then G is fully cycle extendable.Theorem 3.1.1 Let G be a 5-vertices connected graph with G ≥9, thenG is fully cycle extendable.Theorem 3.1.1′ Let G satisfy the conditions κ (G )= G?4 and G ≥9,then G is fully cycle extendable.Theorem 3.1.2 Let G be a 6-vertices connected graph with G ≥11,then G is fully cycle extendable.Theorem 3.1.2′ Let G satisfy the conditions κ (G )= G?5 and G ≥11,then G is fully cycle extendable.Based on the above theorems, I put forward the conjectures as following:Conjecture3.1.1 Let G be a s-vertices connected graph withG ≥ 2 s?1, then G is fully cycle extendable.Conjecture3.1.1′ Let G satisfy the conditions κ (G )= G?s+1 andG ≥ 2 s?1, then G is fully cycle extendable.Conjecture3.1.1′′ Let G be a s-vertices connected graph with?????≤? +2s G1, then G is fully cycle extendable.Conjecture3.1.1′′ ′ Let G satisfy the condition ?????≥? +2κ (G )G1, thenG is fully cycle extendable.