GENERALIZED EXPONENTS OF NON-PRIMITIVE GRAPHS

The exponent of a primitive digraph is the smallest integer k such tha t for each ordered pair of (not necessarily distinct) vertices x and y there is a walk of length k from x to y. As a generalization of expon ent, Brualdi and Liu (Linear Algebra Appl. 14 (1990) 483-499) introduc ed three types of generalized exponents for primitive digraphs in 1990 . In this paper we extend their definitions of generalized exponents f rom primitive digraphs to general digraphs which are not necessarily p rimitive. We give necessary and sufficient conditions for the finitene ss of these generalized exponents for graphs (undirected, correspondin g to symmetric digraphs) and completely determine the largest finite v alues and the exponent sets of generalized exponents for the class of non-primitive graphs of order n, the class of connected bipartite grap hs of order n and the class of trees of order n. (C) 1998 Elsevier Sci ence Inc. All rights reserved.