Connectivity Of Graph And Extensibility Of Path And Cycle Of Graph

Path and cycle are two basic structures of graph, meanwhile, they are also effective tools to analyze graph. Many practical problems can be summed up to study of path and cycle in graphs. The Hamilton problem one of the three famous hard problems in graph theory that is also path and cycle problem in nature. The study on graphs' path and cycle is always the active field in graph. In resent years, the studies about this mainly focused on: cycle problem and path problem. In detail, the studies on this mainly focused on: Hamilton cycle, ancyclicity, ertices pancyclicity, cycle extensibility, longest cycle, Hamilton connected, path extensibility, longest path etc. The study of path and cycle has made great progress, the result and advances in this aspect can be referred to [2]-[16]. The study about these natures mainly focused on two aspects: one aspect is to study the sufficient condition of these natures and the other is to study these natures on some special graphs.The concept of connectivity was put forward earlier, it is an important index sign of depct "the degree of connexion". We can imagine that the graph can possess all kinds natures of path and cycle if the connectivity of graph is high enough in comparison with the order of the graph, all kinds of path and cycle natures will be changed or will be not exsit no long with connectivity reduce gradually, then the problem what is the infimun of connectivity that can possess all kinds of path and cycle natures is worthy of note and study naturally. But in the course of the study about properties of path and cycle, the study on this is still fewer as yet.In order to look for the relation between connectivity and fully cycle extensibility, Liu Xiaoyan studied fully cycle extensibility of graph with the connectivityκ(G)=|G|-3,κ(G)=|G|-4,κ(G)=|G|-5 in 2006, and got these results:定理1[2] Let G satisfies the conditionsκ(G)=|G|-3 and |G|≥7, then G is fully cycle extensible.定理2[2] Let G satisfies the conditionsκ(G)=|G|-4 and |G|≥9, then G is fully cycle extensible.定理3[2] Let G satisfies the conditionsκ(G)=n-5且|G|≥11, then G is fully cycle extensible.According to the law included in the results above, Liu Xiaoyan put forward the following conjecturel[2]:Conjecture 1 Let G satisfies the conditionsκ(G)=|G|-s+1 and |G|≥2s-1, then G is fully cycle extensible.She explained that if conjecture 1 is establish then the infimum of connectivity is the best possible. We renamed the the conjecture 1 as theorem 4, and get theorem 5 further.Theorem 4 Let G satisfies the conditionsκ(G)=|G|-s+1 and |G|≥2s-1, then G is fully cycle extensible.Theorem 5 Let G satisfies the conditionsκ(G)≥(|G|+1)／2, then G is fully cycle extensibleIf theorem 4, theorem 5 are establish then the infimun of connectivity is the best possible. Clearly theorem 4 and theorem 5 is equal.This paper continued Liu Xiaoyan' research, mainly do the two aspets work, prove theorem 4 and theorem 5 at first.Theorem 4, theorem 5 announced the law of relation between fully cycle extensible and connectivity.On the other hand, in order to look for the relaction between path extensible and connectivity, imitate Liu Xiaoyan' way of thinking study path extensible of graph with connectivityκ(G)=|G|-3,κ(G)=|G|-4,κ(G)=|G|-5 and get these results:Theorem 6 Let G satisfies the conditionsκ(G)=|G|-3 and |G|≥7, then G is path extensible.Theorem 7 Let G satisfies the conditionsκ(G)=|G|-4 and |G|≥9, then G is path extensible.Theorem 8 Let G satisfies the conditionsκ(G)=|G|-5 and |G|≥11, then G is path extensible.According to the law included in the results above, the following conjecture were put forward:Conjecture 2 Let G satisfies the conditionsκ(G)=|G|-s+1 and |G|≥2s-1, then G is path extensible.Inmitate theorem 5, we get conjecture 3.Conjecture 3 LetG satisfies the conditionκ(G)≥(|G|+1)／2 then G is path extensible.Conjecture2 includes theorem 4, it was saide that if conjecture is establish then the infimum of connectivity is the best possible.It is regret that we meet some difficulty in particular case in the course of prove conjecture 2 and conjecture 3, this prove is still uncompleted by the end of this thesis is completed for the reson of time.This thesis is divided into two chapter. In the first chapter, we give which are used in this paper, research background, some known result. In the second chapter, we study the relaction between path extensible, fully cycle extensible and connectivity, prove mainly lemma 2, lemma 3, theorem 4, theorem 5, theorem 6, theorem 7, theorem 8.