The existence of planar hypotraceable oriented graphs

Van Aardt, Susan A. ; Burger, Alewyn Petrus ; Frick, Marietjie (2017)

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

Article

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/105362
This item appears in the following collections: