On the exponent of a primitive digraph
A digraph D is primitive iff there is an integer \(k>0\) such that for all ordered pairs of vertices i,j\(\in V(D)\) there is a walk from i to j with length k. The least such k is called the exponent \(\gamma\) of the primitive digraph and satisfies \(\gamma \leq n+s(n-2)\) with n the number of vertices and s the length of the shortest elementary circuit of D. Two of the problems that are studied: Characterize the primitive digraphs on n vertices with shortest circuit length s and exponent \(n+s(n-2).\) If D is a primitive digraph on n vertices with shortest circuit length \(s\geq 2\) and exponent \(\gamma =n+s(n-2),\) does D contain an elementary circuit of length n?
scientific article; zbMATH DE number 3884196