Applied graph theory

About the lower bounds for the number of additional arcs in a minimal vertex 1-extension of oriented path

M. B. Abrosimov, O. V. Modenova

Saratov State University

Abstract: A graph $G^*$ with $n + k$ vertices is vertex $k$-extension of a graph $G$ if every graph obtained by removing any $k$ vertices from $G^*$ contains $G$; it is called minimal vertex $k$-extension of $G$ if it has the least number of arcs among all vertex $k$-extensions of graph $G$ with $n+k$ vertices. A lower bound for the number of additional arcs in minimal vertex 1-extension of an oriented path is given.

Keywords: graph, minimal vertex extension, fault tolerance.

UDC: 519.17