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...
Saved in:
Published in: | Journal of graph theory 2022-05, Vol.100 (1), p.50-68 |
---|---|
Main Authors: | , , , , |
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!
|
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 |