Primitive digraphs with smallest large exponent Original Research Article

A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies αnless-than-or-equals, slantγ(D)less-than-or-equals, slantwn, where αn=left floorwn/2right floor+2 and wn=(n-1)2+1. It is shown that the minimum number of arcs in a primitive digraph D on ngreater-or-equal, slanted5 vertices with exponent equal to αn is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent αn and n+2 arcs. These constructions extend to digraphs with some exponents between αn and wn. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent αn and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2.