Back to search

University of Waterloo

Finding a Second Hamiltonian cycle in Barnette Graphs

Abstract

dc:description.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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Haddadan, Arash

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9630

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Haddadan, Arash. Finding a Second Hamiltonian cycle in Barnette Graphs. University of Waterloo, 2015. http://hdl.handle.net/10012/9630