Properties of minimal primitive digraphs

V. M. Fomichev

Prikladnaâ diskretnaâ matematika, no. 2 (2015), pp. 86-96

Résumé

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.

Détail

Mots-clés : primitive matrix
Keywords: primitive digraph, strongly connected digraph.