Geodesic
Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 19 (2019) no. 4, pp. 479-486 
M. B. Abrosimov; I. A. Kamil; A. A. Lobov. Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 19 (2019) no. 4, pp. 479-486. http://geodesic.mathdoc.fr/item/ISU_2019_19_4_a9/
@article{ISU_2019_19_4_a9,
     author = {M. B. Abrosimov and I. A. Kamil and A. A. Lobov},
     title = {Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {479--486},
     year = {2019},
     volume = {19},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2019_19_4_a9/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - I. A. Kamil
AU  - A. A. Lobov
TI  - Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2019
SP  - 479
EP  - 486
VL  - 19
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/ISU_2019_19_4_a9/
LA  - ru
ID  - ISU_2019_19_4_a9
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A I. A. Kamil
%A A. A. Lobov
%T Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2019
%P 479-486
%V 19
%N 4
%U http://geodesic.mathdoc.fr/item/ISU_2019_19_4_a9/
%G ru
%F ISU_2019_19_4_a9

Voir la notice de l'article provenant de la source Math-Net.Ru

In 1976 John P. Hayes proposed a graph model for investigating the fault tolerance of discrete systems. The technical system is mapped to a graph. The elements of the system correspond to the vertices of the graph, and links between the elements correspond to edges or arcs of the graph. Failure of a system element refers to the removal of the corresponding vertex from the system graph along with all its edges. Later together with Frank Harary the model was extended to links failures. The formalization of a fault-tolerant system implementation is the extension of the graph. The graph $G^*$ is called the vertex $k$-extension of the graph $G$ if after removing any $k$ vertices from the graph $G^*$ result graph contains the graph $G$. A vertex $k$-extension of the graph $G$ is called minimal if it has the least number of vertices and edges among all vertex $k$-extensions of the graph $G$. An algorithm for constructing all nonisomorphic minimal vertex $k$-extensions of the given graph using the method of canonical representatives is proposed.

[1] J. P. Hayes, “A graph model for fault-tolerant computing system”, IEEE Transactions on Computers, C-25:9 (1976), 875–884 | DOI | MR

[2] F. Harary, J. P. Hayes, “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[3] M. B. Abrosimov, Fault tolerance graph models, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp. (in Russian)

[4] A. M. Bogomolov, V. N. Salii, Algebraic foundations of the theory of discrete systems, Nauka, M., 1997, 368 pp. (in Russian) | MR

[5] M. B. Abrosimov, “On the complexity of some problems related to graph extensions”, Math. Notes, 88:5 (2010), 619–625 | DOI | DOI | MR | Zbl

[6] M. B. Abrosimov, “Minimal graph extensions”, New Information Technologies in the Study of Discrete Structures (Tomsk, 2000), 59–64 (in Russian)

[7] M. B. Abrosimov, Minimal extension of graphs with 4, 5, 6 and 7 vertices, VINITI 06.09.2000, No 2352-V00, Saratov State University, Saratov, 2000, 26 pp. (in Russian)

[8] G. Brinkmann, “Isomorphism rejection in structure generation programs”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 51 (2000), 25–38 | DOI | MR | Zbl

[9] B. D. McKay, A. Piperno, “Practical Graph Isomorphism, II”, Journal of Symbolic Computation, 60 (2014), 94–112 | DOI | MR | Zbl

[10] Volga Regional Center for New Information Technologies (in Russian) (accessed 1 May 2019)

[11] Graph World (in Russian) (accessed 1 May 2019)