Publications in Scientific Journals:
B. Klocker, H. Fleischner, G. Raidl:
"A lower bound for the smallest uniquely hamiltonian planar graph with minimum degree three";
Applied Mathematics and Computation,
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.