Applied graph theory

On digraphs with a small number of arcs in a minimal $1$-vertex extension

M. B. Abrosimov, O. V. Modenova

Saratov State University, Saratov

Abstract: A graph $G^*$ nodes is vertex extension of graph $G$ with $n$ nodes if every graph obtained by removing any vertex from $G^*$ contains $G$. Vertex extension of graph $G$ with $n+1$ vertices is called minimal if among all vertex extensions of graph $G$ with $n+1$ vertices it has the minimum possible number of edges. We study digraphs, whose minimal vertex extensions have a specified number of additional arcs. A solution is given when the number of additional arcs is equal to one or two.

UDC: 519.17