The order of hypotraceable oriented graphs

A digraph of order n is hypotraceable if it is nontraceable but all its induced subdigraphs of order n − 1 are traceable. Grötschel et al. (1980) [M. Grötschel, C. Thomassen, Y. Wakabayashi, Hypotraceable digraphs, J. Graph Theory 4 (1980) 377–381] constructed an infinite family of hypotraceable oriented graphs, the smallest of which has order 13. We show that there exist hypotraceable oriented graphs of order n for every n ≥ 8 except possibly for n = 9 , 11 and that K 2 ¯ is the only one of order less than 8. rmore, we determine all the hypotraceable oriented graphs of order 8 and explain the relevance of these results to the problem of determining, for given k ≥ 2 , the maximum order of nontraceable oriented digraphs each of whose induced subdigraphs of order k is traceable.