Article ID Journal Published Year Pages File Type
4602749 Linear Algebra and its Applications 2008 13 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory