Cite this article as:
Abrosimov M. B. Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension . Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2013, vol. 13, iss. 2, pp. 3-9. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-3-9
Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension
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 withn+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.
1. Abrosimov M. B. Grafovye modeli otkazoustoichivosti
[Graph models of fault tolerance]. Saratov, Saratov Univ.
Press, 2012, 192 p. (in Russian).
2. Hayes J. P. A graph model for fault-tolerant computing
system. IEEE Trans. Comput., 1976, vol. C.25, no. 9,
pp. 875–884.
3. Abrosimov M. B. On the Complexity of Some Problems
Related to Graph Extensions. Math. Notes, 2010, vol. 88,
no. 5, pp. 619—625.
4. Abrosimov M. B. Characterization of graphs with a
given number of additional edges in a minimal 1-vertex
extension. Prikladnaya Diskretnaya Matematika [Applied
Discrete Mathematics], 2012, no. 1, pp. 111–120 (in
Russian).
5. Abrosimov M. B. Minimal vertex extensions of directed
stars. Diskr. Mat., 2011, vol. 23, no. 2, pp. 93–102 (in
Russian). DOI: 10.4213/dm1144.
