Some results on generalized exponents

✍ Scribed by Neufeld, Stewart; Shen, Jian

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 241 KB
• Volume: 28
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199808)28:4<215::aid-jgt3>3.0.co;2-m

✦ Synopsis

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 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.