Hamilton cycles in sparse locally connected graphs

DOI10.1016/J.DAM.2018.10.031MaRDI QIDQ1730246zbMATH OpenOpenAlexWikidataFDO

Authors Susan Van Aardt, A. P. Burger, Marietjie Frick, Carsten Thomassen, Johan P. de Wet

Publication date 11 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://backend.orbit.dtu.dk/ws/files/166104136/1_s2.0_S0166218X1830578X_main.pdf

zbMATH Keywords

Hamiltonian cyclelocally connectedNP-completenesspolynomial time algorithm

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• scientific article; zbMATH DE number 672355
• On Hamilton Cycles in Locally Connected Graphs with Vertex Degree Constraints
• A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
• Hamilton Cycles in Planar Locally Finite Graphs
• scientific article; zbMATH DE number 2073563
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• Finding Hamilton cycles in sparse random graphs
• On the Number of Hamilton Cycles in Sparse Random Graphs
• Hamilton cycles in sparse robustly expanding digraphs
• scientific article; zbMATH DE number 4152419

Cites work

• A strengthening of Kikustapos;s theorem
• Complexity of the hamiltonian cycle in regular graph problem
• Extending cycles in graphs
• Graph theory
• Hamiltonian properties of locally connected graphs with bounded vertex degree
• scientific article; zbMATH DE number 3779369 (Why is no real title available?)
• scientific article; zbMATH DE number 3510342 (Why is no real title available?)
• Locally connected graphs

Cited in

(10)

• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• On Hamiltonicity of regular graphs with bounded second neighborhoods
• A note on cycles in locally Hamiltonian and locally Hamilton-connected graphs
• Extending cycles locally to Hamilton cycles
• On Hamilton Cycles in Locally Connected Graphs with Vertex Degree Constraints
• Hamilton Cycles in Planar Locally Finite Graphs
• scientific article; zbMATH DE number 4093499 (Why is no real title available?)
• scientific article; zbMATH DE number 672355 (Why is no real title available?)
• scientific article; zbMATH DE number 5064035 (Why is no real title available?)
• Hamiltonian properties of locally connected graphs with bounded vertex degree

This page was built for publication: Hamilton cycles in sparse locally connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1730246)