For citation:
Abrosimov M. B. Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2013, vol. 13, iss. 2, pp. 3-9. DOI: 10.18500/1816-9791-2013-13-2-2-3-9, EDN: RHABFJ
This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online:
25.05.2013
Full text:
(downloads: 179)
Language:
Russian
Heading:
UDC:
519.17
EDN:
RHABFJ
Characterization of graphs with a small number of additional arcs in a minimal 1-vertex extension
Autors:
Abrosimov Mikhail Borisovich, Saratov State University
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 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.
References:
- Abrosimov M. B. Grafovye modeli otkazoustoichivosti [Graph models of fault tolerance]. Saratov, Saratov Univ. Press, 2012, 192 p. (in Russian).
- Hayes J. P. A graph model for fault-tolerant computing system. IEEE Trans. Comput., 1976, vol. C.25, no. 9, pp. 875–884.
- Abrosimov M. B. On the Complexity of Some Problems Related to Graph Extensions. Math. Notes, 2010, vol. 88, no. 5, pp. 619—625.
- 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).
- 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.
Received:
10.11.2012
Accepted:
17.04.2013
Published:
31.05.2013
Short text (in English):
(downloads: 102)
- 1181 reads