Generalized exponents of primitive symmetric digraphs

✍ Scribed by Richard A. Brualdi; Shao Jia-yu

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 1014 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(96)00077-7

✦ Synopsis

A strongly connected digraph D of order n is primitive (aperiodic) provided the greatest common divisor of its directed cycle lengths equals 1. For such a digraph there is a minimum integer t, called the exponent of D, such that given any ordered pair of vertices x and y there is a directed walk from x to y of length t. The exponent of D is the largest of n 'generalized exponents' that may be associated with D. If D is a symmetric digraph, then D is primitive if and only if its underlying graph is connected and is not bipartite. In this paper we determine the largest value of these generalized exponents over the set of primitive symmetric digraphs whose shortest odd cycle length is a fixed number r. We also characterize the extremal digraphs. Our results are common generalizations of a number of related results in the literature.