Hamiltonian properties of locally connected graphs with bounded vertex degree

DOI10.1016/J.DAM.2010.10.005zbMATH Open1228.05200OpenAlexW2044117898MaRDI QIDQ643015FDOQ643015

Authors: V. S. Gordon, Yury L. Orlovich, Chris N. Potts, V. A. Strusevich 

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

Recommendations

• On Hamilton Cycles in Locally Connected Graphs with Vertex Degree Constraints
• Hamilton cycles in sparse locally connected graphs
• Hamiltonicity of locally Hamiltonian and locally traceable graphs
• scientific article; zbMATH DE number 1535434
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs

zbMATH Keywords

NP-completenessHamiltonian graphlocal connectivity

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites Work

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

Cited In (17)

• Global cycle properties of locally isometric graphs
• Global cycle properties in locally connected, locally traceable and locally Hamiltonian graphs
• Global cycle properties in graphs with large minimum clustering coefficient
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• Title not available (Why is that?)
• Hamiltonian line graphs with local degree conditions
• Disjoint cycles in hypercubes with prescribed vertices in each cycle
• On Hamiltonicity of regular graphs with bounded second neighborhoods
• Hamiltonicity in locally finite graphs: two extensions and a counterexample
• Weakly Hamiltonian-connected locally semicomplete digraphs
• Hamilton cycles in sparse locally connected graphs
• Hamiltonicity of locally Hamiltonian and locally traceable graphs
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• Hamiltonian chordal graphs are not cycle extendable
• On Saito's conjecture and the Oberly-Sumner conjectures
• Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability
• On Hamilton Cycles in Locally Connected Graphs with Vertex Degree Constraints

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

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