## Mathematics Faculty Articles

#### Title

Primitive Digraphs with Smallest Large Exponent

#### Document Type

Article

#### Publication Date

4-1-2008

#### Publication Title

Linear Algebra and its Applications

#### Keywords

Diophantine equation, Large exponent, Primitive digraph

#### ISSN

0024-3795

#### Volume

428

#### Issue/No.

7

#### First Page

1740

#### Last Page

1752

#### Abstract

A primitive digraph *D* on *n* vertices has large exponent if its exponent, γ(D), satisfies α_{n}⩽γ(D)⩽w_{n}, where α_{n}=⌊w_{n}/2⌋+2 and w_{n}=(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 *w*_{n}. 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.

#### NSUWorks Citation

MacGillivray, G.; Nasserasr, Shahla; Olesky, D. D.; and Van Den Driessche, P., "Primitive Digraphs with Smallest Large Exponent" (2008). *Mathematics Faculty Articles*. 98.

http://nsuworks.nova.edu/math_facarticles/98

#### DOI

10.1016/j.laa.2007.10.019

## Comments

## AMS classifications