Hamiltonian properties of locally connected graphs with bounded vertex degree

DOI10.1016/j.dam.2010.10.005zbMath1228.05200OpenAlexW2044117898MaRDI QIDQ643015

Vitaly A. Strusevich, Yury L. Orlovich, Chris N. Potts, Valery S. Gordon

Publication date: 27 October 2011

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

Full work available at URL: https://doi.org/10.1016/j.dam.2010.10.005

zbMATH Keywords

local connectivityNP-completenessHamiltonian graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Related Items (12)

Global cycle properties of locally isometric graphs ⋮ Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs ⋮ On Hamiltonicity of regular graphs with bounded second neighborhoods ⋮ Unnamed Item ⋮ On Saito's conjecture and the Oberly-Sumner conjectures ⋮ Hamiltonicity of locally Hamiltonian and locally traceable graphs ⋮ Disjoint cycles in hypercubes with prescribed vertices in each cycle ⋮ Hamilton cycles in sparse locally connected graphs ⋮ Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability ⋮ The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs ⋮ Global cycle properties in graphs with large minimum clustering coefficient ⋮ Hamiltonian Chordal Graphs are not Cycle Extendable

Cites Work

• Cycles of given length in some \(K_{1,3}\)-free graphs
• Extending cycles in graphs
• Quadrangularly connected claw-free graphs
• Vertex pancyclicity in quasi claw-free graphs
• Hamiltonian properties of triangular grid graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Matching theory
• A note on locally connected and Hamiltonian-connected graphs
• Complement reducible graphs
• The edge Hamiltonian path problem is NP-complete
• Complexity of the hamiltonian cycle in regular graph problem
• Claw-free graphs---a survey
• The complexity of the locally connected spanning tree problem
• Research problems.
• Planar Hamiltonian chordal graphs are cycle extendable
• HAMILTONian circuits in chordal bipartite graphs
• Sufficient condition for Hamiltonicity of \(N_2\)-locally connected claw-free graphs
• A strengthening of Kikustapos;s theorem
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Local properties of graphs
• Updating the hamiltonian problem—A survey
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Almost claw‐free graphs
• Locally connected graphs
• HamiltonianN2-locally connected claw-free graphs
• Hamilton Paths in Grid Graphs
• Hamiltonian circuits in N₂‐locally connected K_1,3‐free graphs
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Cycle Extendability of Hamiltonian Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Hamiltonian properties of locally connected graphs with bounded vertex degree