On Hamilton cycles in locally connected graphs with vertex degree constraints
Tools
Tools
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
Full text not available from this repository.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 |