Planar hypohamiltonian oriented graphs

Alewyn P Burger; Johan P de Wet; Marietjie Frick; Nico Van Cleemput; Carol T Zamfirescu

doi:10.1002/jgt.22765

Planar hypohamiltonian oriented graphs

Alewyn P Burger
, Johan P de Wet
, Marietjie Frick
, Nico Van Cleemput
, Carol T Zamfirescu

University of Stellenbosch
DST‐NRF Centre of Excellence in Mathematical and Statistical Sciences
University of Pretoria
Ghent University
Babes-Bolyai University

Research output: Contribution to journal › Article › peer-review

Abstract

In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many (Formula presented.) it remained an open question whether planar hypohamiltonian oriented graphs of order (Formula presented.) 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.

Original language	English
Pages (from-to)	50-68
Number of pages	19
Journal	Journal of Graph Theory
Volume	100
Issue number	1
DOIs	https://doi.org/10.1002/jgt.22765
Publication status	Published - May 2022
Externally published	Yes

Bibliographical note

Publisher Copyright:
© 2021 Wiley Periodicals LLC

Access to Document

10.1002/jgt.22765

Cite this

@article{315ff5d2cfe9491384e587327cb3b72d,

title = "Planar hypohamiltonian oriented graphs",

abstract = "In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many (Formula presented.) it remained an open question whether planar hypohamiltonian oriented graphs of order (Formula presented.) 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.",

author = "Burger, \{Alewyn P\} and \{de Wet\}, \{Johan P\} and Marietjie Frick and \{Van Cleemput\}, Nico and Zamfirescu, \{Carol T\}",

note = "Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC",

year = "2022",

month = may,

doi = "10.1002/jgt.22765",

language = "English",

volume = "100",

pages = "50--68",

journal = "Journal of Graph Theory",

number = "1",

}

TY - JOUR

T1 - Planar hypohamiltonian oriented graphs

AU - Burger, Alewyn P

AU - de Wet, Johan P

AU - Frick, Marietjie

AU - Van Cleemput, Nico

AU - Zamfirescu, Carol T

PY - 2022/5

Y1 - 2022/5

N2 - In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many (Formula presented.) it remained an open question whether planar hypohamiltonian oriented graphs of order (Formula presented.) 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.

AB - In 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many (Formula presented.) it remained an open question whether planar hypohamiltonian oriented graphs of order (Formula presented.) 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.

UR - https://go.openathens.net/redirector/westernsydney.edu.au?url=https://doi.org/10.1002/jgt.22765

U2 - 10.1002/jgt.22765

DO - 10.1002/jgt.22765

M3 - Article

VL - 100

SP - 50

EP - 68

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Planar hypohamiltonian oriented graphs

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this