Finding a Second Hamiltonian cycle in Barnette Graphs

Parity argument;oik;room-partitioning;exchange algorithm;cubic graph;Barnette"s conjecture;Combinatorics and Optimization

Haddadan, Arash

University of Waterloo

关键词: Parity argument;    oik;    room-partitioning;    exchange algorithm;    cubic graph;    Barnette";    s conjecture;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/9630/1/Haddadan_Arash.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

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.