Properties of minimal primitive digraphs
Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 86-96
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.
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},
year = {2015},
number = {2},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/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