A Decision Condition For The Existence Of A Hamilton Path

Graph theory is a branch of discrete mathematics and combinatorial mathematics, it has very important theoretical and application value. With the rapid development of computer science, graph theory is becoming more and more widely applied.A graph is a collection of points and edges connecting these points.In 1736, the great mathematician Euler solution solved the "Konigsberg seven Bridges problem" and this was the frist paper in graph theory. For figure, there are two very important "traversing" problem, the first is to traverse the graph of each edge just once, the second is traverse points in the graph just once. If the set of each edges is a circuit, then the graph is called an Euler graph.If there is a path passing through each vertex in the graph, then this path is called a Hamiltonian path. If there is a circuit passing though each vertex,the graph is a Hamiltonian path is a loop, it is called a Hamiltonian graph. Euler has successfully solved the Euler graph decision problem. But to decide whether a graph is a Hamiltonian is a NP-compete problemIn this paper, we give a new sufficient condition of the existence of a Hamiltonian path.The first chapter introductes some back ground in this problem.The second chapter presents the concept and basic properties of figure.The third chapter is the focus of this definitons. In 1960 Ore gave a famous a sufficient condition for the existence of the Hamiltonian path: if G is a finite simple graph and, if any pair two adjacent vertices u, v, satisfies d(u)+d(v)?|v(G)|-1 then, there exists a Hamilton path.In the third chapter, we will improved, the result as follows.If G is a simple connected graph and pair of any two vertices u, v, satisfies d(u)+d(v)?|v(G)|-2 then, there exists a Hamilton path.