On Three Conjectures of Thomassen and the Extremal Digraphs for Two Conjectures of Nash‐Williams

ABSTRACT Thomassen suggested the following three conjectures: (1) Every 2‐strong ‐regular digraph of order , except for two exceptional digraphs of orders 5 and 7, is Hamiltonian. (2) Every 3‐strong digraph of order and with a minimum degree of at least is Hamiltonian‐connected. (3) Let be a 4‐strong digraph of order such that the sum of the degrees of every pair of nonadjacent vertices is at least . Then is Hamiltonian‐connected. In this paper, we disprove Conjectures 1 and 2. We prove that: Conjecture 3 is true if and only if every 3‐strong digraph of order which contains a vertex such that for every pair of nonadjacent distinct vertices , is Hamiltonian. We construct infinitely many ‐strong, where , digraphs which show that two famous conjectures of Nash‐Williams and a conjecture of Kühn et al. for Hamiltonicity of digraphs are best possible in the sense that they become false if exactly one of the degree conditions is not valid. This answers the two questions posed by Kühn et al. Moreover, the constructed digraphs also show that the bound on the semidegrees of in the theorems obtained by Thomassen and by the author is the best possible, even with the additional condition that has high connectivity.