Some results on generalized exponents

A digraph G = ( V , E ) is primitive if, for some positive integer k , there is a u → v walk of length k for every pair u , v of vertices of V . The minimum such k is called the exponent of G , denoted exp( G ). The exponent of a vertex u ∈ V , denoted exp( u ), is the least integer k such that there is a u → v walk of length k for each v ∈ V . For a set X ⊆ V , exp( X ) is the least integer k such that for each v ∈ V there is a X → v walk of length k , i.e., a u → v walk of length k for some u ∈ X . Let F ( G , k ) : = max{exp( X ) : | X | = k } and F ( n , k ) : = max{ F ( G , k ) : | V | = n }, where | X | and | V | denote the number of vertices in X and V , respectively. Recently, B. Liu and Q. Li proved F ( n , k ) = ( n − k )( n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k , 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F ( G , k ) = F ( n , k ), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G , Δ + ( G ) = max{ d + ( u ) : u ∈ V }, and thus obtain a new refinement of the Wielandt bound ( n − 1) 2 + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998