On a problem of Lewin (Q1386513): Difference between revisions

A digraph is said to be 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. In a primitive digraph \(G\), the smallest such \(k\) is called the exponent of \(G\), denoted by \(\exp(G)\). The parameter \(j(G)\) 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. Then \(j(G)\leq\exp(G)\). By a theorem of Wielandt, we have \(j(G)\leq n^2- 2n+2\). The present paper gives finer upper bounds on \(j(G)\) as well as an open problem.