Primitive Digraphs with Smallest Large Exponent

Authors

G. MacGillivray, University of Victoria
Shahla Nasserasr, University of VictoriaFollow
D. D. Olesky, University of Victoria
P. Van Den Driessche, University of Victoria

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)²+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.

Comments

AMS classifications

• 05C20;
• 05C50

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.
https://nsuworks.nova.edu/math_facarticles/98

DOI

10.1016/j.laa.2007.10.019