Finding a Second Hamiltonian cycle in Barnette Graphs
Abstract
We study the following two problems: (1) finding a second room-partitioning of an oik, and (2) finding a second Hamiltonian cycle in cubic graphs. The existence of solution for both problems is guaranteed by a parity argument.
For the first problem we prove that deciding whether a 2-oik has a room-partitioning is NP-hard, even if the 2-oik corresponds to a planar triangulation.
For the problem of finding a second Hamiltonian cycle, we state the following conjecture: for every cubic planar bipartite graph finding a second Hamiltonian cycle can be found in time linear in the number of vertices via a standard pivoting algorithm. We fail to settle the conjecture, but we prove it for cubic planar bipartite WH(6)-minor free graphs.
Collections
Cite this version of the work
Arash Haddadan
(2015).
Finding a Second Hamiltonian cycle in Barnette Graphs. UWSpace.
http://hdl.handle.net/10012/9630
Other formats