Exponents of vertex-transitive digraphs (Q1971214): Difference between revisions

The exponent (respectively, diameter) of a directed graph \(D\) is the least value \(r\) such that for all \(u,v\in V(D)\) there exists a directed \((u\to v)\)-walk of length exactly \(r\) (respectively, \(\leq r\)). These parameters are finite when \(D\) is strongly connected. Many upper bounds are presented for these two parameters in terms of order, valence, girth, or connectivity. A typical result is the following. If \(G\) is an abelian group and \(D\) is the directed Cayley graph of \(G\) with respect to a generating set with \(k\geq 4\) elements, and if the exponent is not defined vacuously, then the exponent of \(D\) is at most \(\max\{5,n/\lceil k/2\rceil-1\}\). If this exponent is \(\geq 6\), then equality holds if and only if \(D\) belongs to one of two families of lexicographic products determined by \textit{Y. O. Hamidoune} [Networks 23, No. 4, 283-287 (1993; Zbl 0778.05039)]. It is conjectured, that the exponent (if defined nonvacuously) of a \(k\)-valent directed graph on \(n\) vertices is \(\leq\lfloor n/k\rfloor^2+1\).