Pancyclicity and NP-completeness in planar graphs

DOI10.1016/S0166-218X(99)00163-8MaRDI QIDQ1962068zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Eric Mendelsohn, Mingchu Li, Derek G. Corneil

Publication date 29 June 2000

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

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00163-8

zbMATH Keywords

complexityNP-completenessplanar graphsvertex pancyclicity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• Vertex pancyclic graphs
• scientific article; zbMATH DE number 1744073
• scientific article; zbMATH DE number 867697
• Vertex pancyclic graphs
• scientific article; zbMATH DE number 3857154

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Pairs of edge-disjoint Hamiltonian circuits
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(11)

• 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
• Vertex-pancyclism in edge-colored complete graphs with restrictions in color transitions
• Full cycle extendability of locally connected \(K_{1,4}\)-restricted graphs
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• Pancyclicity in switching classes
• Exact algorithms for finding longest cycles in claw-free graphs
• The Hamilton cycle problem for locally traceable and locally Hamiltonian graphs
• On Saito's conjecture and the Oberly-Sumner conjectures
• scientific article; zbMATH DE number 1504827 (Why is no real title available?)

This page was built for publication: Pancyclicity and NP-completeness in planar graphs

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