Computational results on the traceability of oriented graphs of small order (Q396945): Difference between revisions

Summary: A digraph \(D\) is traceable if it contains a path visiting every vertex, and hypotraceable if \(D\) is not traceable, but \(D-v\) is traceable for every vertex \(v\in V(D)\). \textit{S. A. Van Aardt} et al. [Discrete Math. 311, No. 14, 1273--1280 (2011; Zbl 1225.05122)] showed that there exists a hypotraceable oriented graph of order \(n\) for every \(n\geq 8\), except possibly for \(n=9\) or \(11\). These two outstanding existence questions for hypotraceable oriented graphs are settled in this paper -- the first in the negative and the second in the affirmative. 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\leq 6\) every \(k\)-traceable oriented graph is traceable and that for \(k=7\) and each \(k\geq 9\) there exist nontraceable \(k\)-traceable oriented graphs of order \(k+1\). The traceability conjecture states that for \(k\geq 2\) every \(k\)-traceable oriented graph of order \(n\geq 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\leq n\leq 32\).