Planar hypohamiltonian oriented graphs

dc.contributor.authorBurger, Alewyn P.
dc.contributor.authorDe Wet, J.P. (Johan)
dc.contributor.authorFrick, Marietjie
dc.contributor.authorVan Cleemput, Nico
dc.contributor.authorZamfirescu, Carol T.
dc.date.accessioned2023-05-30T04:53:43Z
dc.date.available2023-05-30T04:53:43Z
dc.date.issued2023
dc.description.abstractIn 1978 Thomassen asked whether planar hypohamiltonian oriented graphs exist. Infinite families of such graphs have since been described but for infinitely many it remained an open question whether planar hypohamiltonian oriented graphs of order 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.en_US
dc.description.departmentMathematics and Applied Mathematicsen_US
dc.description.librarianhj2023en_US
dc.description.sponsorshipResearch Foundation Flanders; VSC(Flemish Supercomputer Center);DST‐NRF Centre of Excellence in Mathematical and Statistical Sciences.en_US
dc.description.urihttp://wileyonlinelibrary.com/journal/jgten_US
dc.identifier.citationA.P. Burger, J.P. de Wet, M. Frick, N. Van Cleemput, and C.T. Zamfirescu, Planar hypohamiltonian oriented graphs,Journal of Graph Theory 2022; 100: 50–68. https://doi.org/10.1002/jgt.22765.en_US
dc.identifier.issn0364-9024 (print)
dc.identifier.issn1097-0118 (online)
dc.identifier.other10.1002/jgt.22765
dc.identifier.urihttp://hdl.handle.net/2263/90965
dc.language.isoenen_US
dc.publisherWileyen_US
dc.rights© 2021 Wiley Periodicals LLC. This is the pre-peer reviewed version of the following article : (name of article), Journal name, vol. , no. , pp. , 2022, doi : . The definite version is available at : http://wileyonlinelibrary.com/journal/jgt [12 months embargo]en_US
dc.subjectHypohamiltonianen_US
dc.subjectHypotraceableen_US
dc.subjectOiented graphen_US
dc.subjectPlanaren_US
dc.titlePlanar hypohamiltonian oriented graphsen_US
dc.typePostprint Articleen_US

Files

Original bundle

Now showing 1 - 2 of 2
Thumbnail Image
Name:
Burger_Planar_2022.pdf
Size:
1.49 MB
Format:
Adobe Portable Document Format
Description:
Postprint Article
Download
Thumbnail Image
Name:
Burger_PlanarAppenA_2022.pdf
Size:
152.55 KB
Format:
Adobe Portable Document Format
Description:
Appendix A
Download

License bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Research Articles (Mathematics and Applied Mathematics)
Research Articles (University of Pretoria)
Simple item page