The Existence of Planar Hypotraceable Oriented Graphs

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$.

Keywords

• planar
• hypohamiltonian
• hypotraceable
• oriented graph
• msc 05c10, 05c20, 05c38
• [math] mathematics [math]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]