On Hamiltonian powers of digraphs
For a strongly connected digraph \(D\), the \(k\)th power \(D^k\) of \(D\) is the digraph, whose vertex set is the same as \(D\) and whose edge set is such that there is a directed edge from \(x\) to \(y\) in \(D^k\) if the directed distance from \(x\) to \(y\) in \(D\) is less than or equal to \(k\). Ghouila-Houri showed that \(D^k\) is Hamiltonian for every digraph \(D\) on \(n\) vertices and for every \(k\geq n/2\). The present paper characterizes these digraphs \(D\) of odd order, whose \((\lceil n/2\rceil-1)\)th power is Hamiltonian.
scientific article; zbMATH DE number 1436042