This article is cited in 4 papers

Computer science

Characterization of graphs with a small number of additional arcs in a minimal $1$-vertex extension

M. B. Abrosimov, O. V. Modenova

Saratov State University, Russia, 410012, Saratov, Astrahanskaya st., 83

Abstract: A graph $G^*$ is a $k$-vertex extension of a graph $G$ if every graph obtained from $G^*$ by removing any $k$ vertices contains $G$. $k$-vertex extension of a graph $G$ with $n+k$ vertices is called minimal if among all $k$-vertex extensions of $G$ with $n+k$ vertices it has the minimal possible number of arcs. We study directed graphs, whose minimal vertex $1$-extensions have a specific number of additional arcs. A solution is given when the number of additional arcs equals one or two.

Key words: minimal vertex extension, exact extension, fault tolerance, graph theory.

UDC: 519.17

DOI: 10.18500/1816-9791-2013-13-2-2-3-9

Bibliographic databases:

•