Computational results on the traceability of oriented graphs of small order

A digraph D is traceable if it contains a path visiting every vertex, and hypotrace- able if D is not traceable, but D v is traceable for every vertex v 2 V (D). Van Aardt, Frick, Katreni~c and Nielsen [Discrete Math. 11(2011), 1273-1280] showed that there exists a hypotraceable oriented graph of order n for every n > 8, except possibly for n = 9 or 11. These two outstanding existence questions for hypotraceable oriented graphs are settled in this paper | the rst in the negative and the second in the a rmative. Furthermore, D is k-traceable if D has at least k vertices and each of its induced subdigraphs of order k is traceable. It is known that for k 6 6 every k-traceable oriented graph is traceable and that for k = 7 and each k > 9 there exist nontraceable k-traceable oriented graphs of order k + 1. The Traceability Conjecture states that for k > 2 every k-traceable oriented graph of order n > 2k 1 is traceable. In this paper it is shown via computer searches that all 7-traceable and 8-traceable oriented graphs of orders 9, 10 and 11 are traceable, and that all 9-traceable oriented graphs of order 11 are traceable. All hypotraceable graphs of order 10 are also found. Recently, these results are used to prove that the Traceability Conjecture also holds for k = 7; 8 and 9, except possibly when k = 9 and 22 6 n 6 32.National Research Foundation, grant number GUN 77248