On a problem of Lewin

✍ Scribed by Jian Shen; Stewart Neufeld

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 864 KB
• Volume: 274
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(97)00389-3

✦ Synopsis

A digraph G is called primitive if for some positive integer k there is a walk of length exactly k from each vertex u to each vertex o (possibly u again). If G is primitive, the smallest such k is called the exponent of G, denoted by exp(G). In 1971, M. Lewin introduced the paramater 1(G) for a primitive digraph G. It is thy smallest k for which there is both a walk of length k and a walk of length k + 1 fronr some vertex II to some vertex o (possibly II again). Clearly Z(G) < exp(G) and so 1(G) < n7 -2n + 2 by a theorem of Wielandt. Finer upper bounds on I(G) are <given, and an open problem is presented.