Remarks on Hamiltonian properties of powers of digraphs (Q1329819)

The \(k\)th power \(G^ k\) of a digraph \(G\) has the same vertices as \(G\), and there is an arc from \(x\) to \(y\) in \(G^ k\) if there is some directed \(x\)-\(y\) path of length at most \(k\) in \(G\). The present paper deals with Hamiltonian properties of powers of digraphs. In contrast to the situation in the undirected case, where \(G^ 3\) is Hamiltonian connected for every connected graph \(G\) [\textit{M. Sekanina}, Publ. Fac. Univ. Brno 142, 137-140 (1960)], no such result is possible in the directed case. In fact, it is shown that for every positive integer \(k\) there is some strongly connected digraph \(G\) such that \(G^ k\) does not contain any Hamiltonian path. Despite this negative result, some affirmative result is possible for directed cacti---digraphs where for every pair \((x,y)\) of vertices there is exactly one directed \(x\)-\(y\) path. It is proven that the third power \(G^ 3\) of every directed cactus \(G\) is Hamiltonian connected.