A diameter bound on the exponent of a primitive directed graph

AbstractA directed graph G is primitive if there exists a positive integer k such that for every pair of vertices u, v ∈ G there is a walk from u to v of length k. The least such k is called the exponent of G. We define Gk to be the directed graph having the same vertex set as G and arcs (u, v) if and only if there is a walk in G of length k from vertex u to vertex v. A well-known upper bound for the exponent of a primitive directed graph G of order n is (n − 1)2 + 1, due to H. Wielandt in 1950. Our main result is the following refinement of the Wielandt bound: If G is a primitive directed graph with diameter d, then the exponent of G is at most d2 + 1. We construct the primitive graphs for which equality is attained, and we generalize the bound to the class of irreducible matrices. In the course of proving the main result we find the following, which is interesting in its own right: If G is a primitive directed graph with diameter d, then the diameter of Gk is at most d for all positive integers k