# Hamiltonian properties of locally connected graphs with bounded vertex degree

Gordon, Valery S., Orlovich, Yury L., Potts, Chris N. and Strusevich, Vitaly A.
(2011)
*Hamiltonian properties of locally connected graphs with bounded vertex degree.*
Discrete Applied Mathematics, 159 (16).
pp. 1759-1774.
ISSN 0166-218X
(doi:10.1016/j.dam.2010.10.005)

## Abstract

We consider the existence of Hamiltonian cycles for the 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) ⩽ 4. We show that every connected, locally connected graph with Δ(G) = 5 and δ(G) ⩾ 3 is fully cycle extendable which extends the results of Kikust [P.B. Kikust, The existence of the Hamiltonian circuit in a regular graph of degree 5, Latvian Math. Annual 16 (1975) 33–38] and Hendry [G.R.T. Hendry, A strengthening of Kikust’s theorem, J. Graph Theory 13 (1989) 257–260] on full cycle extendability of the connected, locally connected graphs with the maximum vertex degree bounded by 5. Furthermore, we prove that problem Hamilton Cycle for the locally connected graphs with Δ(G) ⩽ 7 is NP-complete.

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

Additional Information: | [1] Accepted: 9 October 2010. [2] First published online: 13 November 2010. [3] Published in print: 28 September 2011. [4] This paper was first presented at the 8th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009). [5] Discrete Applied Mathematics is The Journal of Combinatorial Algorithms, Informatics and Computational Sciences. |

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

Subjects: | Q Science > QA Mathematics T Technology > T Technology (General) |

School / Department / Research Groups: | School of Computing & Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences Faculty of Architecture, Computing & Humanities > School of Computing & Mathematical Sciences > Department of Mathematical Sciences |

Related URLs: | |

Last Modified: | 15 Jul 2014 11:26 |

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

### Actions (login required)

View Item |