[Back]

B. Klocker, H. Fleischner, G. Raidl:
"A lower bound for the smallest uniquely hamiltonian planar graph with minimum degree three";
Applied Mathematics and Computation, 380 (2020), 1 - 19.

Bondy and Jackson conjectured in 1998 that every planar uniquely hamiltonian graph must have a vertex of degree two. In this work we verify computationally Bondy and Jackson´s conjecture for graphs with up to 25 vertices. Using a reduction we search for graphs that contain a stable fixed-edge cycle or equivalently a stable cycle with one vertex of degree two. For generating candidate graphs we use plantri and for checking if they contain a stable fixed-edge cycle we propose three approaches. Two of them are based on integer linear programming (ILP) and the other is a cycle enumeration algorithm. To reduce the search space we prove several properties a minimum planar graph with minimum degree at least three containing a stable fixed-edge cycle must satisfy, the most significant being triangle freeness. Comparing the three algorithms shows that the enumeration is more effective on small graphs while for larger graphs the ILP-based approaches perform better. Finally, we use the enumeration approach together with plantri to check that there does not exist a planar graph with minimum degree at least three which contains a stable fixed- edge cycle with 24 or fewer vertices.

http://dx.doi.org/10.1016/j.amc.2020.125233

https://publik.tuwien.ac.at/files/publik_301803.pdf