Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Cyclic Properties of Locally Connected Graphs with Bounded Vertex Degree

SpeakerValery Gordon

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.