Hamiltonicity exponent of digraphs. (English) Zbl 0855.05081

Summary: Initiated by Sekanina, in the sixties and more intensively in the seventies there were considered powers of undirected graphs with special respect to their Hamiltonian behaviour. These investigations have resulted in a lot of interesting and partly very profound propositions; we only remind of the (simple) result of Sekanina that the cube of every finite connected graph is Hamiltonian connected, or of the famous theorem of Fleischner that the square of any nontrivial block is Hamiltonian. For directed graphs (digraphs), the situation is completely different; till not long ago nobody was seriously engaged in studying the analogous problem for digraphs. The main reason for this situation is that for digraphs, these questions become much more complicated than in the undirected case. This paper intends to discuss some of the difficulties arising in the case of digraphs and to present some beginning results.


05C45 Eulerian and Hamiltonian graphs
05C20 Directed graphs (digraphs), tournaments
Full Text: EuDML EMIS