Geodesic
Construction of all minimal edge extensions of the graph with isomorphism rejection
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 20 (2020) no. 1, pp. 105-115 
M. B. Abrosimov; H. H. K. Sudani; A. A. Lobov. Construction of all minimal edge extensions of the graph with isomorphism rejection. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 20 (2020) no. 1, pp. 105-115. http://geodesic.mathdoc.fr/item/ISU_2020_20_1_a8/
@article{ISU_2020_20_1_a8,
     author = {M. B. Abrosimov and H. H. K. Sudani and A. A. Lobov},
     title = {Construction of all minimal edge extensions of the graph with isomorphism rejection},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {105--115},
     year = {2020},
     volume = {20},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2020_20_1_a8/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - H. H. K. Sudani
AU  - A. A. Lobov
TI  - Construction of all minimal edge extensions of the graph with isomorphism rejection
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2020
SP  - 105
EP  - 115
VL  - 20
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/ISU_2020_20_1_a8/
LA  - ru
ID  - ISU_2020_20_1_a8
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A H. H. K. Sudani
%A A. A. Lobov
%T Construction of all minimal edge extensions of the graph with isomorphism rejection
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2020
%P 105-115
%V 20
%N 1
%U http://geodesic.mathdoc.fr/item/ISU_2020_20_1_a8/
%G ru
%F ISU_2020_20_1_a8

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

In 1993 Frank Harary and John P. Hayes proposed a graph model for investigating edge 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. The formalization of a fault-tolerant system implementation is the extension of the graph. The graph $G^*$ is called the edge $k$-extension of the graph $G$ if, after removing any $k$ edges from the graph $G^*$ result graph contains the graph $G$. The edge $k$-extension of a graph $G$ is called minimal if it has the least number of vertices and edges among all edge $k$-extensions of a graph $G$. An algorithm for constructing all nonisomorphic minimal edge $k$-extensions of a given graph using methods of canonical representatives and Read–Faradjev are proposed.

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

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

[3] Abrosimov M. B., Fault tolerance graph models, Izdatel'stvo Saratovskogo universiteta, Saratov, 2012, 192 pp. (in Russian)

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

[5] Abrosimov M. B., “On the Complexity of Some Problems Related to Graph Extensions”, Math. Notes, 88:5 (2010), 619–625 | DOI | DOI

[6] Abrosimov M. B., Kamil I. A. K., Lobov A. A., “Construction of All Nonisomorphic Minimal Vertex Extensions of the Graph by the Method of Canonical Representatives”, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 19:4 (2019), 479–486 (in Russian) | DOI

[7] Abrosimov M. B., “Minimal graph extensions”, New information technologies in the study of discrete structures, Izdatel'skii dom Tomskogo gosudarstvennogo universiteta, Tomsk, 2000, 59–64 (in Russian)

[8] Abrosimov M. B., 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)

[9] Brinkmann G., “Isomorphism rejection in structure generation programs”, Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 51, 2000, 25–38 | DOI

[10] McKay B. D., Graph formats, (accessed 1 May 2019) http://users.cecs.anu.edu.au/bdm/data/formats.html

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

[12] Volga Regional Center for New Information Technologies (in Russian) (accessed 1 May 2019) http://prcnit.sgu.ru

[13] Graph World (in Russian) (accessed 1 May 2019) http://graphworld.ru