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:https://doi.org/10.1016/j.endm.2007.07.028)

Full text not available from this repository.

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
Pre-2014 Departments:	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:	Publisher Organisation
Last Modified:	30 Sep 2019 15:11
URI:	http://gala.gre.ac.uk/id/eprint/1210

Actions (login required)

View Item