2017/10/19 by Heping Jiang, Jiang, Heping
Computer Science · Engineering · #05C45 05C85 #Advanced Graph Theory Research #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1710.06974
openalex publication_date 2017/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Deciding if a graph is a Hamilton graph, also named the Hamilton cycle problem, is important for discrete mathematics and computer science. Due to no characterization to identify Hamilton graphs effectively, there are no tractable algorithms to solve the Hamilton cycle problem. Grinberg Theorem is a necessary condition only for planar Hamilton graphs. In this paper, based on new studies on the Grinberg Theorem, in which we provided new properties of Hamilton graphs with respect to the cycle bases and improved the Grinberg Theorem to derive an efficient condition for Hamilton graphs, we present a new precise algorithm for deciding Hamilton graphs, named the '1+1' algorithm. Theoretically, the '1+1' algorithm terminates in O(|E(G)|3) worst time complexity, where |E(G)| is the size of the given graph G.