Aperiodic Graph - Testing For Aperiodicity

Testing For Aperiodicity

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 V_i where i is the length (taken mod 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 V_i has the property that each edge in the graph goes from a set V_i 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:

• Perform a depth-first search of G
• For each e in G that connects a vertex on level i of the depth-first search tree to a vertex on level j, let k_e = j - i - 1.
• Compute the greatest common divisor of the set of numbers k_e.

The graph is aperiodic if and only if the period computed in this fashion is 1.

If G is not strongly connected, we may perform a similar computation in each strongly connected component of G, ignoring the edges that pass from one strongly connected component to another.

Jarvis and Shier describe a very similar algorithm using breadth first search in place of depth-first search; the advantage of depth-first search is that the strong connectivity analysis can be incorporated into the same search.