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)⩽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.

Comments

AMS classifications

  • 05C20;
  • 05C50

DOI

10.1016/j.laa.2007.10.019