Methods for finding minimal primitive extensions of directed graphs

A.A. Ripinen, M.B. Abrosimov


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.

Full Text:

PDF (Russian)


Bogomolov A.M., Salii V.N. Algebraicheskie osnovy teorii diskretnykh sistem. M.: Nauka 1997.

Frobenius G. Über Matrizen aus nicht negativen Elementen // Sitzungsber. Preuß. Akad. Wiss., Berlin, 1912. P. 456–477.

Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642–648.

Fomichev V.M. Otsenki eksponentov primitivnykh grafov // Prikladnaia diskretnaia matematika. 2011. №2(12). S. 101–112.

Fomichev V.M. O stepennoi strukture grafov // Prikladnaia diskretnaia matematika, 2015, №8. S. 20–22.

Fomichev V.M. Svoistva minimal'nykh primitivnykh orgrafov // Prikladnaia diskretnaia matematika. 2015. №2(28). S. 86–96.

Salii V.N. Minimal'nye primitivnye rasshireniia orientirovannykh grafov. // Prikladnaia diskretnaia matematika. 2008. C. 116-119.

Dulmage A.L., Mendelsohn N.S. The exponent of a primitive matrix // Canad. Math. Bull. 1963. Vol. 5, № 3. P. 241–244.

Brualdi R., Ryser H. Combinatorial Matrix Theory. Cambridge University Press, New York, 1991.

Sachkov V.N., Tarakanov V.E. Kombinatorika neotritsatel'nykh matrits. M.: TVP, 2000.


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162