On a conjecture of Lewin's problem
Let \(l(G)\) denote the smallest \(k\) such that there exist walks from \(u\) to \(v\) of lengths \(k\) and \(k+1\) for some vertices \(u,v\) of a directed graph \(G.\) \textit{J. Shen} and \textit{S. Neufeld} [Linear Algebra Appl. 274, 411-426 (1998; Zbl 0901.05049)] conjectured that if \(G\) is a primitive directed graph nonisomorphic to the complete graph with loop at each vertex then \(\exp(G)\geq 2\cdot l(G).\) The authors of this paper prove an undirected version of the conjecture above and they characterize all primitive undirected graphs for which the identity \(\exp(G)= 2\cdot l(G)\) is attained.
scientific article; zbMATH DE number 1586481