Loading…

Planar hypohamiltonian oriented graphs

In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many n it remained an open question whether planar hypohamiltonian oriented graphs of order n exist. In this paper we develop new methods for co...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2022-05, Vol.100 (1), p.50-68
Main Authors: Burger, Alewyn P., Wet, Johan P., Frick, Marietjie, Van Cleemput, Nico, Zamfirescu, Carol T.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many n it remained an open question whether planar hypohamiltonian oriented graphs of order n exist. In this paper we develop new methods for constructing hypohamiltonian digraphs, which, combined with efficient graph generation algorithms, enable us to fully characterise the orders for which planar hypohamiltonian oriented graphs exist. Our novel methods also led us to discover the planar hypohamiltonian oriented graph of smallest order and size, as well as infinitely many hypohamiltonian orientations of maximal planar graphs. Furthermore, we answer a question related to a problem of Schiermeyer on vertex degrees in hypohamiltonian oriented graphs, and characterise all the orders for which planar hypotraceable oriented graphs exist.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22765