On a conjecture of Lewinʹs problem Original Research Article

Let digraph G be a primitive digraph. The parameter l(G) introduced by M. Lewin [Numer. Math. 18 (1971) 154] is the smallest positive integer k for which 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 vertexu to each vertex v in G. J. Shen and S. Neufeld [Linear Algebra Appl. 274 (1998) 411] conjectured exp(G)/l(G)greater-or-equal, slanted2 except G congruent with Kn* (complete graph with loop at each vertex). In this paper, the conjecture was proved for undirected graph, and all primitive undirected graphs attaining this lower bound were characterized.