Hamiltonian properties of locally connected graphs with bounded vertex degree |
| |
| Authors: | Valery S Gordon Chris N Potts |
| |
| Institution: | a United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganova Str., 220012 Minsk, Belarusb Department of Discrete Mathematics and Algorithmics, Faculty of Applied Mathematics and Computer Science, Belarusian State University, Nezavisimosti Ave. 4, 220030 Minsk, Belarusc School of Mathematics, University of Southampton, Highfield, Southampton, SO17 1BJ, UKd School of Computing and Mathematical Sciences, University of Greenwich, Old Royal Naval College, Park Row, London, SE10 9LS, UK |
| |
| 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. |
| |
| Keywords: | Hamiltonian graph Local connectivity NP-completeness |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
