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 Graphs

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

    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: planar,hypohamiltonian,Hypotraceable,oriented graph,MSC 05C10, 05C20, 05C38,[MATH] Mathematics [math],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Consultation statistics

    This page has been seen 461 times.
    This article's PDF has been downloaded 348 times.