Pancyclicity And Dominating Hamilton Connectedness In Graphs

Pancyclic graph and hamilton-connected graph always are important topics in graph theory Hamilton problem because of rich theoretical significance and strong mathematical modeling value.Hamilton problem is NP-complete,scholars research related theorem mainly from two aspects of parameter conditions and structure con-ditions,they have achieved many famous theorem yet.Among them,the Hamilton problem about forbidden subgraph has been popular science in the academic world,and the latest progress of its research can be referred to[2]-[8].In this paper,we consider graph structure and forbidden subgraph condition to characterize the pancyclicity and dominating hamilton connectedness.In the first chapter,mainly carries on the symbol inform.In the second chapter,using the theorem proved by zheng wei et al:Let G be a 3K1-free graph with at least three vertices.If G is 2-connected,then G is pancyclic,unless G is isomorphic to C4 or C5.On this basis,we increase the connectivity and the number of |V(G)| of forbidden subgraph at the same time to prove the establishment of the relevant conclusion.Firstly,we convert the graph structure condition with the forbidden subgraph 4K1 into a parameter condition with the independent number a of 1,2 or 3.This paper mainly study independent number ?=.In the first section,we characterize the existence of(k+1)-cycle when k?[6,n-1]by using mathematical ideas such as recursion and counterproof.For any cycle C in G,we establish the following mapping::f((C)=max {|S?V(C)?:S as any largest 3-independent set in G,}.Among them,the choice of C makes f(C)as large as possible.According to the definition of f(C),the value of this function is f(C)?{0,1,2,3}.In the proof,classification demonstration will be conducted according to the value of its function.In the second section,considering the existence of 3-cycle to 6-cycle and describing the structure of the neighborhood and neighborhood union of C by using the pigeonhole principle and classification discussion.Comprehensive sections to prove that graph G is pancyclic.In the three chapter,we prove the following theorem:letG be 3-connected claw-free graph.If ?(G)=2,then G is dominating hamilton-connected.We firstly define new concept:dominating hamilton-connected graph.Let S is any minimum dominating set of graph G,if any pair vertices of V(G)\S as the endpoint exist hamilton path,then graph G is dominating hamilton-connected.In the first section,under the condition of the longest non-hamilton path,the path structure is characterized by improving the path neighborhood.In the second section,according to the relative position of the given arbitrary minimum dominating set S and the longest path,we carry out case analysis.The establishment of the property is described in two sections.In the four chapter,mainly carries on the induction prospect.One,Whether we can generalize the conclusion of ?=3,4K1-free graph to the pancyclicity of ?=k,(k+1)K1-free graph.Two,the complexity of hamilton connectedness is proved to be far beyond normal operation by positive characterization of the graph structure,For the problem that the dominating set element is the endpoint,whether we can suggest a new direction.For the above two problems,whether we can transform the condition with the forbidden subgraph,independent number and dominating number into the line graph condition to improve the conclusions.