Skip navigation
The Australian National University

Planar hypohamiltonian graphs on 40 vertices

Mohammadreza Jooyandeh (ANU,Research School of Computer Science)

CS HDR MONITORING

DATE: 2012-11-30
TIME: 10:00:00 - 10:30:00
LOCATION: CSIT Seminar Room, N101
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
Bounding the order of the smallest planar hypohamiltonian graph has proved to be a challenging problem for the past four decades. Prior to the present study, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. We improve upon this by generating 25 planar hypohamiltonian graphs of order 40. Using this, we present planar hypotraceable graphs of order 154; previously, the smallest known example had 162 vertices. Moreover, it had been proven that there is a planar hypohamiltonian (hypotraceable) graph of order n for every n >= 76 (n >= 180). Using the new result obtained in this study, we decreased these best bounds to 42 and 156, respectively.


BIO:



Updated:  13 November 2012 / Responsible Officer:  JavaScript must be enabled to display this email address. / Page Contact:  JavaScript must be enabled to display this email address.