Exponents of vertex-transitive digraphs
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\).
This page was built for publication: Exponents of vertex-transitive digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971214)
