|
This article is cited in 4 scientific papers (total 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.
Citation:
M. B. Abrosimov, O. V. Modenova, “Characterization of graphs with a small number of additional arcs in a minimal $1$-vertex extension”, Izv. Saratov Univ. Math. Mech. Inform., 13:2(2) (2013), 3–9
Linking options:
https://www.mathnet.ru/eng/isu406 https://www.mathnet.ru/eng/isu/v13/i4/p3
|
|