Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
DOI10.1007/s00373-019-02101-7zbMath1436.05056OpenAlexW2977973604MaRDI QIDQ2308511
Akira Suyama, Robert D. Barish
Publication date: 3 April 2020
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-019-02101-7
planar graphsHamiltonian cyclesHamiltonicitycounting complexity4-regular graphs4-connected graphsquartic graphs\#P completeness4-vertex-connected graphs
Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)
Related Items (1)
Cites Work
- Unnamed Item
- The complexity of computing the permanent
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Some simplified NP-complete graph problems
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes.
- Vertices of small degree in uniquely Hamiltonian graphs
- The relative complexity of approximate counting problems
- Counting substrate cycles in topologically restricted metabolic networks
- Regular \(n\)-valent \(n\)-connected non-Hamiltonian non \(n\)-edge-colourable graphs
- Uniquely Hamiltonian Graphs of Minimum Degree 4
- The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs
- A Dichotomy Theorem for Polynomial Evaluation
- A Theorem on Planar Graphs
- The Complexity of Enumeration and Reliability Problems
- #P-COMPLETENESS VIA MANY-ONE REDUCTIONS
- The Planar Hamiltonian Circuit Problem is NP-Complete
- On the maximum number of cycles in a planar graph
- On Unapproximable Versions of $NP$-Complete Problems
- On Hamiltonian Circuits
- A theorem on paths in planar graphs
This page was built for publication: Counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs
