# On Hamilton cycles in locally connected graphs with vertex degree constraints

Tools

Orlovich, Yury L., Gordon, Valery S., Potts, Chris N. and Strusevich, Vitaly A. (2007) *On Hamilton cycles in locally connected graphs with vertex degree constraints.* Electronic Notes in Discrete Mathematics, 29. pp. 169-173. ISSN 1571-0653 (doi:10.1016/j.endm.2007.07.028)

Official URL: http://www.sciencedirect.com/science/article/B75GV...

## Abstract

It is shown that every connected, locally connected graph with the maximum vertex degree Δ(G)=5 and the minimum vertex degree δ(G)3 is fully cycle extendable. For Δ(G)4, all connected, locally connected graphs, including infinite ones, are explicitly described. The Hamilton Cycle problem for locally connected graphs with Δ(G)7 is shown to be NP-complete

Item Type: | Article |
---|---|

Uncontrolled Keywords: | Hamiltonian graph, local connectivity, NP-completeness |

Subjects: | Q Science > QA Mathematics |

School / Department / Research Groups: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Related URLs: | |

Last Modified: | 31 Mar 2011 18:20 |

URI: | http://gala.gre.ac.uk/id/eprint/1210 |

### Actions (login required)

View Item |