On Hamilton Cycles in Locally Connected Graphs with Vertex Degree Constraints

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 p...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2007-08, Vol.29, p.169-173
Main Authors: Orlovich, Yury L., Gordon, Valery S., Potts, Chris N., Strusevich, Vitaly A.
Format: Article
Language:English
Subjects:
Hamiltonian graph
local connectivity
NP-completeness
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2007.07.028