Exponents of the primitive Boolean matrices with fixed girth

Abstract

The $girth$ of a primitive Boolean matrix is defined to be the $girth$ of its associated digraph. In this paper, among all primitive Boolean matrices of order $n$, the primitive exponents of those of girth $g$ are considered. For the primitive matrices of both order $n\ge 10$ and girth $g>\frac{n^2-4n}{4(n-3)}$, the matrices with primitive exponents in $[2n-2+(g-1)(n-3),n+g(n-2)]$ are completely characterized.

arXiv comment6 pages