一些新的Hamilton图的必要条件

A Series of New Necessary Conditions for a Graph to Be Hamiltonian

寻求Hamilton图的适当的特征刻画是图论的一个重大未解决问题,根据图的结构特征,设计了图的顶点的分层方法,研究了Hamilton图中层与层间对外顶点数和对外边数应该满足的关系,分析了Hamilton图中每层顶点数与每层对外顶点数的关系,探讨了图与其Hamilton演化图的Hamilton性关系,最后得到一些新的Hamilton图的必要条件。所获得的新的Hamilton图的必要条件实用性强,使用方便,能判断一些原必要条件不能判断的非Hamilton图。

It is not solved what specific property of a Hamiltonian graph is. Depending on structural properties of a graph, a way to divide vertices of the graph into several groups is designed. It is studied that the relationship between number of vertices and bounds of the before layer and number of vertices and bounds of the next layer. The relationship between a graph and its Hamihonian evolutionary graph is researched. Some results concerning necessary condition for a graph to be Hamiltonian are proved. It is proved that the new necessary conditions for a graph to be Hamiltonian are not only efficient but also convenient. We show how the results give an easy proof of the nonexistence of a Hamiltonian cycle in the Petersen graph.