The existence of planar hypotraceable oriented graphs
Date
2017
Journal Title
Journal ISSN
Volume Title
Publisher
Discrete Mathematics & amp; Theoretical Computer Science
Abstract
A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph D is \emph{hypotraceable} if D is not traceable but D−v is traceable for every vertex v∈V(D). It is known that there exists a planar hypotraceable digraph of order n for every n≥7, but no examples of planar hypotraceable oriented graphs (digraphs without 2-cycles) have yet appeared in the literature. We show that there exists a planar hypotraceable oriented graph of order n for every even n≥10, with the possible exception of n=14.
Description
CITATION: Van Aardt, S. A., Burger, A. P. & Frick, M. 2017. The existence of planar hypotraceable oriented graphs. Discrete Mathematics and Theoretical Computer Science, 19(1):1-10, doi:10.23638/DMTCS-19-1-4.
The original publication is available at https://dmtcs.episciences.org
The original publication is available at https://dmtcs.episciences.org
Keywords
Hypotraceable digraphs, Directed graphs
Citation
Van Aardt, S. A., Burger, A. P. & Frick, M. 2017. The existence of planar hypotraceable oriented graphs. Discrete Mathematics and Theoretical Computer Science, 19(1):1-10, doi:10.23638/DMTCS-19-1-4