The exponent and circumdiameter of primitive directed graphs

The exponent of a primitive directed graph (digraph) D, denoted lambda(D), is the smallest m such that for each ordered pair of vertices (u, v), there exists a u ↝ v walk of length m. A walk touches another if they have a vertex in common. If lambda(D) is the set of all cycle lengths, then the circumdiameter of D, denoted dc(lambda(D)), is the maximum over all ordered pairs of vertices (u, v) of the length of a shortest u ↝ v walk that touches cycles of all lengths. It is well known that gamma(D) ≤ &phis;(lambda( D)) + dc(lambda(D)), in which &phis;(lambda(D)) is the Frobenius-Schur index. The main results of this thesis include several new sufficient conditions and families of digraphs for which equality holds in the above upper bound. A primitive digraph D on n vertices has large exponent if gamma(D) ≥ &fll0;n-12 +12&flr0; + 2. Additional sufficient conditions for equality in the above upper bound for gamma(D) and a new upper bound for d c(lambda(D)) are given for digraphs with large exponent. Expressions for the exponent, diameter and circumdiameter of some primitive digraphs on n vertices with large exponent and circumference n or n - 1 are also given.