Primitive directed graph

Primitive directed graph --- примитивный орграф.

1. A digraph [math]\displaystyle{ D }[/math] is primitive if there exists an integer [math]\displaystyle{ k }[/math] such that there is a walk [math]\displaystyle{ u \rightarrow v }[/math] of length [math]\displaystyle{ k }[/math] for every pair [math]\displaystyle{ u,v \in V }[/math]. The least such [math]\displaystyle{ k }[/math] is called the exponent of [math]\displaystyle{ D }[/math], denoted [math]\displaystyle{ \gamma(D) }[/math]. The local exponent of [math]\displaystyle{ D }[/math] at a vertex [math]\displaystyle{ u \in V }[/math], denoted by [math]\displaystyle{ \exp_{D}(u) }[/math], is the least integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ u \rightarrow v[k] }[/math] (a walk of length [math]\displaystyle{ k }[/math]) for each [math]\displaystyle{ v \in V }[/math].

2. The index and period of a given digraph [math]\displaystyle{ D }[/math] are the minimum nonnegative integer [math]\displaystyle{ k = k(D) }[/math] and the minimum positive integer [math]\displaystyle{ p = p(D) }[/math] such that for any ordered pair of vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] there is a walk of length [math]\displaystyle{ k }[/math] from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] if and only if there is a walk of length [math]\displaystyle{ k + p }[/math] from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] in [math]\displaystyle{ D }[/math]. A digraph [math]\displaystyle{ D }[/math] is primitive if [math]\displaystyle{ D }[/math] is strongly connected and [math]\displaystyle{ p(D) = 1 }[/math].