A diameter bound on the exponent of a primitive directed graph (Q1923184): Difference between revisions

A directed graph \(G\) is primitive if there exists a positive integer \(k\) such that for every pair of vertices \(u,v\in G\) there is a walk from \(u\) to \(v\) of length \(k\). The least such \(k\) is called the exponent of \(G\). We define \(G^k\) 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 \(d^2+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 \(G^k\) is at most \(d\) for all positive integers \(k\).