On traceable powers of digraphs (Q1970584)

Let \(D\) be a (finite) strongly connected digraph. The \(m\)th power of \(D\) is the digraph \(D^m\) with the same set of vertices as \(D\) and an ordered pair \((x,y)\) of different vertices is an arc of \(D^m\) whenever the directed distance from \(x\) to \(y\) in \(D\) is no more than \(m\). A digraph is said to be traceable if it contains a hamiltonian (directed) path. Denote by \(\alpha(D)\) the independence number of a digraph \(D\). The authors state the following conjecture: Let \(D\) be a strongly connected digraph of order \(n\geq 4\) and \(m=\lfloor n/2\rfloor-1\). If \(\alpha(D^m)\leq m+1\) then \(D^m\) is traceable. They prove the conjecture for \(n=2m+2\) even. Moreover, it is shown that if \(D\) is a strongly connected digraph of order \(n=2m+2\geq 4\), then \(D^m\) is traceable if and only if \(D\) is not isomorphic to a digraph of a family explicitly constructed.