Hamiltonian properties of locally connected graphs with bounded vertex degree

DOI10.1016/J.DAM.2010.10.005MaRDI QIDQ643015zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

NP-completenessHamiltonian graphlocal connectivity

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

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

Cites work

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 3857154 (Why is no real title available?)
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 4051623 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3779369 (Why is no real title available?)
• scientific article; zbMATH DE number 3510342 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3641494 (Why is no real title available?)
• scientific article; zbMATH DE number 1161243 (Why is no real title available?)
• scientific article; zbMATH DE number 932198 (Why is no real title available?)
• scientific article; zbMATH DE number 1409241 (Why is no real title available?)
• A note on locally connected and Hamiltonian-connected graphs
• A strengthening of Kikustapos;s theorem
• Almost claw‐free graphs
• Claw-free graphs---a survey
• Complement reducible graphs
• Complexity of the hamiltonian cycle in regular graph problem
• Cycle Extendability and Hamiltonian Cycles in Chordal Graph Classes
• Cycle Extendability of Hamiltonian Interval Graphs
• Cycles of given length in some \(K_{1,3}\)-free graphs
• Every connected, locally connected nontrivial graph with no induced claw is hamiltonian
• Extending cycles in graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Graph theory
• HAMILTONian circuits in chordal bipartite graphs
• Hamilton Paths in Grid Graphs
• Hamiltonian circuits in N₂‐locally connected K_1,3‐free graphs
• Hamiltonian properties of triangular grid graphs
• HamiltonianN2-locally connected claw-free graphs
• Local properties of graphs
• Locally connected graphs
• Matching theory
• Planar Hamiltonian chordal graphs are cycle extendable
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Quadrangularly connected claw-free graphs
• Research problems.
• Sufficient condition for Hamiltonicity of \(N_2\)-locally connected claw-free graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The complexity of the locally connected spanning tree problem
• The edge Hamiltonian path problem is NP-complete
• Updating the hamiltonian problem—A survey
• 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
• scientific article; zbMATH DE number 1535434 (Why is no real title available?)
• 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
• Hamilton cycles in sparse locally connected graphs
• Weakly Hamiltonian-connected locally semicomplete digraphs
• 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)