On a problem of Lewin
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.
- The proof of a conjecture on the Lewin number of primitive non-powerful signed digraphs
- The base sets of primitive zero-symmetric sign pattern matrices
- The Lewin index set of primitive digraphs with order \(n\) and girth \(3\)
- scientific article; zbMATH DE number 5533333 (Why is no real title available?)
- The extremal primitive digraph with both Lewin index n-2 and girth 2 or 3.
- On a conjecture of Lewin's problem
- A note on Lewin's problem
This page was built for publication: On a problem of Lewin
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386513)
