On the Hamiltonicity exponent of directed cacti Original Research Article

For a digraph G, the kth power Gk can be defined in a similar way as in the case of undirected graphs. If G is finite and strongly connected, eH(G) := min{k : Gk is Hamiltonian} is called the Hamiltonicity exponent of G; analogously, further exponents-for instance, the Hamiltonian connectedness exponent eHC(G)—can be introduced. In order to get nontrivial upper bounds for these exponents it is sensible to consider appropriate subclasses of strongly connected digraphs. In this paper some problems of this kind are treated for directed cacti, i.e. finite strongly connected digraphs every edge of which is contained in at most one directed cycle. Especially, we give a characterization of unicyclic directed cacti G fulfilling eH(G)⩽2.