Graphs generalizing closed curves with linear construction of the Hamiltonian cycle Parametrization of discretized curves

AbstractMotivated by questions from digital topology, we present a particular class of graphs, here called a good graphs, in which there exists a unique Hamiltonian cycle. Then we observe some more properties of these graphs. Finally, we provide a linear algorithm (with respect to the number of vertices) which — depending on the graph G — either proves G is not a good graph, or constructs a Hamiltonian cycle in G