Hamiltonian properties of locally connected graphs with bounded vertex degree

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2011-09, Vol.159 (16), p.1759-1774
Main Authors: Gordon, Valery S., Orlovich, Yury L., Potts, Chris N., Strusevich, Vitaly A.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Circuits
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Extensibility
Graph theory
Graphs
Hamiltonian graph
Information retrieval. Graph
Local connectivity
Mathematical analysis
Mathematics
NP-completeness
Sciences and techniques of general use
Strengthening
Theorems
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2010.10.005