The Existence of Planar Hypotraceable Oriented GraphsArticle
Authors: Susan van Aardt 1; Alewyn Petrus Burger 2; Marietjie Frick 1
NULL##NULL##NULL
Susan van Aardt;Alewyn Petrus Burger;Marietjie Frick
- 1 Department of Mathematical Sciences [South Africa]
- 2 Department of Logistics [Stellenbosch]
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$.
Volume: Vol. 19 no. 1
Section: Graph Theory
Published on: March 16, 2017
Accepted on: December 9, 2016
Submitted on: February 17, 2017
Keywords: MSC 05C10, 05C20, 05C38, [MATH]Mathematics [math], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] planar, hypohamiltonian, Hypotraceable, oriented graph