The Existence of Planar Hypotraceable Oriented Graphs
Susan van Aardt (1), Alewyn Petrus Burger (2) (3), Marietjie Frick (1)
(1) Department of Mathematical Sciences [South Africa]
(2) Department of Logistics [Stellenbosch]
(3) Department of Logistics [Stellenbosch University]
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\in V(D)$. It is known that there exists a planar hypotraceable digraph of order $n$ for every $n\geq 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 \geq 10$, with the possible exception of $n = 14$.
