A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three

DOI10.1016/J.AMC.2020.125233MaRDI QIDQ2180685zbMATH OpenOpenAlexFDO

Authors Benedikt Klocker, Herbert Fleischner, Günther R. Raidl

Publication date 14 May 2020

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2020.125233

zbMATH Keywords

integer linear programmingminimum counterexamplestable cyclesuniquely hamiltonian graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45) Linear programming (90C05) Integer programming (90C10)

Recommendations

• Graphs with few Hamiltonian cycles
• A degree constraint for uniquely Hamiltonian graphs
• Vertices of small degree in uniquely Hamiltonian graphs
• scientific article; zbMATH DE number 4016941
• On uniquely Hamiltonian claw-free and triangle-free graphs

Cites work

• A degree constraint for uniquely Hamiltonian graphs
• Cell-probe lower bounds for the partial match problem
• Fast generation of planar graphs
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• scientific article; zbMATH DE number 1312984 (Why is no real title available?)
• scientific article; zbMATH DE number 2086643 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• On Hamiltonian Circuits
• Solution of a Large-Scale Traveling-Salesman Problem
• Spanning cycles of nearly cubic graphs
• Uniquely Hamiltonian graphs of minimum degree 4
• Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
• Vertices of small degree in uniquely Hamiltonian graphs

Cited in

(2)

• Any maximal planar graph with only one separating triangle is Hamiltonian
• Graphs with few Hamiltonian cycles

Describes a project that uses

Uses Software

• plantri

This page was built for publication: A lower bound for the smallest uniquely Hamiltonian planar graph with minimum degree three

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