Susan van Aardt ; Alewyn Petrus Burger ; Marietjie Frick - The Existence of Planar Hypotraceable Oriented Graphs

dmtcs:1310 - Discrete Mathematics & Theoretical Computer Science, March 16, 2017, Vol. 19 no. 1 - https://doi.org/10.23638/DMTCS-19-1-4
The Existence of Planar Hypotraceable Oriented GraphsArticle

Authors: Susan van Aardt 1; Alewyn Petrus Burger 2; Marietjie Frick 1

  • 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 Dv is traceable for every vertex vV(D). It is known that there exists a planar hypotraceable digraph of order n for every n7, 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 n10, 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: planar,hypohamiltonian,Hypotraceable,oriented graph,MSC 05C10, 05C20, 05C38,[MATH]Mathematics [math],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 711 times.
This article's PDF has been downloaded 590 times.