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

作者：

Highlights：

• New algorithms for finding uniquely hamiltonian cycles.

• Transforming stable fixed edge cycles to uniquely hamiltonian cycles.

• Strong properties of a minimum counter example to Bondy and Jackson’s conjecture.

• Verifies Bondy and Jackson’s conjecture for graphs with up to 25 vertices.

摘要

•New algorithms for finding uniquely hamiltonian cycles.•Transforming stable fixed edge cycles to uniquely hamiltonian cycles.•Strong properties of a minimum counter example to Bondy and Jackson’s conjecture.•Verifies Bondy and Jackson’s conjecture for graphs with up to 25 vertices.

论文关键词：Uniquely hamiltonian graphs,Integer Linear programming,Stable cycles,Minimum counterexample

论文评审过程：Received 27 September 2019, Revised 11 March 2020, Accepted 15 March 2020, Available online 16 April 2020, Version of Record 16 April 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125233