Aperiodic graph

Suppose that G is strongly connected and that k divides the lengths of all cycles in G. Consider the results of performing a depth-first search of G, starting at any vertex, and assigning each vertex v to a set Vi where i is the length (taken modulo k) of the path in the depth-first search tree from the root to v. It can be shown (Jarvis & Shier 1996) that this partition into sets Vi has the property that each edge in the graph goes from a set Vi to another set V(i + 1) mod k. Conversely, if a partition with this property exists for a strongly connected graph G, k must divide the lengths of all cycles in G. Thus, we may find the period of a strongly connected graph G by the following steps: The graph is aperiodic if and only if the period computed in this fashion is 1.

In a strongly connected graph, if one defines a Markov chain on the vertices, in which the probability of transitioning from v to w is nonzero if and only if there is an edge from v to w, then this chain is aperiodic if and only if the graph is aperiodic.

A Markov chain in which all states are recurrent has a strongly connected state transition graph, and the Markov chain is aperiodic if and only if this graph is aperiodic.

Aperiodicity is also an important necessary condition for solving the road coloring problem.

According to the solution of this problem (Trahtman 2009), a strongly connected directed graph in which all vertices have the same outdegree has a synchronizable edge coloring if and only if it is aperiodic.