Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

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:
download
(downloads: 136)
Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17
DOI: 
10.18500/1816-9791-2013-13-2-2-3-9
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. 

Key words: 
minimal vertex extension
exact extension
fault tolerance
graph theory
References: 
  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.
Received: 
10.11.2012
Accepted: 
17.04.2013
Published: 
31.05.2013
Short text (in English):
download
(downloads: 72)
  • 928 reads