On a conjecture of Lewin's problem

Let digraph G be a primitive digraph. The parameter l(G) introduced by M. L ewin [Numer. Math. 18 (1971) 154] is the smallest positive integer k for wh ich there are both a walk of length k and a walk of length k + 1 from some vertex u to some vertex v. As we know, the exponent of G is the smallest k such that there is a walk of length exactly k from each vertex u to each ve rtex v in G. J. Shen and S. Neufeld [Linear Algebra Appl. 274 (1998) 411] c onjectured exp(G)/l(G) greater than or equal to 2 except G congruent to K-n * (complete graph with loop at each vertex). In this paper, the conjecture was proved for undirected graph, and all primitive undirected graphs attain ing this lower bound were characterized. (C) 2001 Published by Elsevier Sci ence Inc, All rights reserved.