Hamiltonian properties of locally connnected graphs with bounded vertex degree

Abstract

We consider the existence of hamiltonian cycles for locally connected graphs with a bounded vertex degree. For a graph G, let ¢(G) and ±(G) denote the maximum and minimum vertex degrees, respectively. We explicitly describe all connected, locally connected graphs with ¢(G) 6 4. We show that every connected, locally connected graph with ¢(G) = 5 and ±(G) > 3 is fully cycle extendable which extends the results of P.B. Kikust (Latvian Math. Annual 16 (1975) 33{38) and G.R.T. Hendry (J. Graph Theory 13 (1989) 257{260) on fully cycle extendability of connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for locally connected graphs with ¢(G) 6 7 is NP-complete. 2000 Mathematics Subject Classi¯cation: 05C38 (05C45, 68Q25).