Local exponents of primitive digraphs

✍ Scribed by Jian Shen; Stewart Neufeld

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 492 KB
• Volume: 268
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(97)00036-0

✦ Synopsis

A digraph G = (V, E) is primitive i[~ for some positive integer k, there is a u ~ ~; walk of length k for evew pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The local exponent of G at a vertex u ~ V, denoted expc(u), is the least integer k such that there is a u --* v walk of length k for each v ~ V. Let V = {1, 2 ..... n}. Following Brualdi and Liu, we order the vertices of V so that expc:(1) 4 expc(2) ~< "" 4 expc.(n) = exp(G). It is known that exp¢:(k) <~ s(n -2) + k for all k, 1 ~< k ~< n. The problem of characterizing the exponent set ES. = {exp(G) : G ~ ~n}, where .~,, is the set of" all primitive digraphs of order n, has been completely settled. We define the ith local exponent set ESn(i) := {expc.(i) : G ~9~} for each i, 1 <~ i <~ n, and show that ES,,(1) has a characterization which closely parallels that of ESn(n) = ES.. We conjecture that, except for minor ehanges, there are similar fornmlae for the ES.(i) for all 1 ~< i ~< n.