On a problem of Lewin Original Research Article

A digraph G is called primitive if for some positive integer k there is a walk of length exactly k from each vertex u to each vertex v (possibly u again). If G is primitive, the smallest such k is called the exponent of G, denoted by exp(G). In 1971, M. Lewin introduced the paramater l(G) for a primitive digraph G. It is the smallest k for which there is both a walk of length k and a walk of length k + 1 from some vertex u to some vertex v (possibly u again). Clearly l(G) less-than-or-equals, slant exp(G) and so l(G) less-than-or-equals, slant n2 − 2n + 2 by a theorem of Wielandt. Finer upper bounds on l(G) are given, and an open problem is presented.