Primitive Digraphs with Smallest Large Exponent
Linear Algebra and its Applications
Diophantine equation, Large exponent, Primitive digraph
A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies αn⩽γ(D)⩽wn, where αn=⌊wn/2⌋+2 and wn=(n-1)2+1. It is shown that the minimum number of arcs in a primitive digraph D on n⩾5 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.
MacGillivray, G.; Nasserasr, Shahla; Olesky, D. D.; and Van Den Driessche, P., "Primitive Digraphs with Smallest Large Exponent" (2008). Mathematics Faculty Articles. 98.