Exponents of vertex-transitive digraphs
type: Item
instance of: scholarly article
title: Exponents of vertex-transitive digraphs
zbMATH Open document ID: 0942.05025
DOI: 10.1016/S0012-365X(99)00291-5
author: J. Shen
author: D. A. Gregory
published in: Discrete Mathematics
publication date: 2000-08-15T00:00:00Z
review text: 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\).
reviewed by: Mark E. Watkins
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1421660
zbMATH Keywords: exponent
zbMATH Keywords: Cayley digraph
zbMATH Keywords: strongly connected
zbMATH Keywords: vertex-transitive
zbMATH Keywords: girth
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00291-5
OpenAlex ID: W2132290920
description: scientific article; zbMATH DE number 1421660