Methods for finding minimal primitive extensions of directed graphs

Abstract

A graph G is called primitive if all vertices in it are mutually reachable in the same number of steps. The concept of primitivity was originally formulated for matrices and naturally extended to graphs when considering a graph as an adjacency matrix. Research on primitive graphs is being actively pursued in various directions. For example, estimates of the exponents of primitive graphs are made, the power structure of primitive graphs and their other properties are considered. It follows from the definition that a primitive graph is strongly connected. In this regard, in order to find the minimal primitive extension, it is necessary to check for the presence of a minimal strongly coupled extension, which is primitive. In the case when there is no such extension, a well-known algorithm for an arbitrary minimal strongly coupled extension can be used. The criterion for primitiveness of a graph is well known: a graph is primitive if and only if the greatest common divisor of all its cycles is equal to one. In this paper, we will propose an algorithm for transforming the original graph, in which the largest common divisor of all cycles does not change, to simplify the search for the minimal primitive extension for individual classes of graphs, the asymptotic complexity of which is O(m), where m is the number of arcs in the graph.