Geodesic
Properties of minimal primitive digraphs
Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 86-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that, for $n\ge4$, the complexity of the determination of all $n$-vertex minimal primitive digraphs, which are parts of a given $n$-vertex primitive digraph $\Gamma$, coincides with the complexity of the recognition of a monotone Boolean function in $s$ variables where $s$ is the number of arcs $(i,j)$ in $\Gamma$ such that the vertex $i$ out-degree and the vertex $j$ in-degree exceed 1. It is found that, for $n\ge4$, all the primitive $n$-vertex digraphs with $n+1$ arcs are minimal graphs and there are minimal primitive $n$-vertex digraphs with the number of arcs from $n+2$ to $2n-3$. Minimal primitive $n$-vertex digraphs with $n+1$ and $n+2$ arcs are described.
Mots-clés : primitive matrix
Keywords: primitive digraph, strongly connected digraph. 
@article{PDM_2015_2_a8,
     author = {V. M. Fomichev},
     title = {Properties of minimal primitive digraphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {86--96},
     publisher = {mathdoc},
     number = {2},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_2_a8/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - Properties of minimal primitive digraphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 86
EP  - 96
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_2_a8/
LA  - ru
ID  - PDM_2015_2_a8
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T Properties of minimal primitive digraphs
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 86-96
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_2_a8/
%G ru
%F PDM_2015_2_a8
V. M. Fomichev. Properties of minimal primitive digraphs. Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 86-96. http://geodesic.mathdoc.fr/item/PDM_2015_2_a8/

[1] Bar-Gnar R. I., Fomichev V. M., “About the minimal primitive matrices”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2014, no. 7, 7–9 (in Russian)

[2] Varfolomeev A. A., Fomichev V. M., Information Security. Mathematical Foundations of Cryptology, Part I, MEPhI Publ., Moscow, 1995, 114 pp. (in Russian)

[3] Fomichev V. M., “The estimates of exponents for primitive graphs”, Prikladnaya Diskretnaya Matematika, 2011, no. 2(12), 101–112 (in Russian)

[4] Harary F., Graph Theory, AW, 1969 | MR