Cyclic Properties of Locally Connected Graphs with Bounded Vertex Degree
Co-authorsYury Orlovich and Chris Potts
We consider the existence of Hamiltonian cycles for locally connected graphs with bounded vertex degree. Let D(G) and d(G) denote, respectively, the maximum and minimum vertex degree of graph G. We explicitly describe all connected, locally connected graphs with D(G)<5. We show that every connected, locally connected graph with D(G)=5 and d(G)>2 is fully cycle extendable. Furthermore, we prove that the HAMILTONIAN CYCLE problem for locally connected graphs with D(G)<8 is NP-complete.