Computational experiment on constructing fault-tolerant graph implementations with up to 9 vertices

I.A.K. Kamil


In many applications, failure of a critical element of technical device or system where computers are used, outages or malfunctions can be expensive or even disastrous and can lead to progressive collapse. It is necessary to provide the ability to tolerate faults by detecting failures and isolate defect modules so that the rest of the system can operate correctly. That is, such a system should be fault-tolerant. To study the problem of complete fault tolerance in 1976 J.P. Hayes proposed a graph-based model. Later in 1993 and 1996 J.P. Hayes together with F. Harary proposed two models: for node fault tolerance (NFT) and for edge fault tolerance ( EFT). In this paper, we study only a model for element failures. The construction of a system resistant to the failure of k elements means the construction of a vertex k-extension for a graph corresponding to the system. Optimality requires that the number of additional elements (vertices) and the connections between them (edges) be as small as possible. The task of constructing minimal vertex k-extensions is computationally complex. This article will present the results of constructing graphs from vertices of small size to up to 9 vertices and minimal vertex 2-extensions for 7- and 8-vertex graphs. In addition, we present results on extensions of meshes and tori with up to 12 vertices.

Full Text:

PDF (Russian)


Hayes J. P. A graph model for fault-tolerant computing system / J. P. Hayes // IEEE Transactions on Computers, 1976. Vol. C-25, No 9. P. 875–884.

Harary F., Hayes J. P. Node fault tolerance in graphs // Networks. 1996. Vol.27. P.19-23.

Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol.23. P. 135-142.

Abrosimov M.B. Grafovye modeli otkazoustoichivosti. Saratov : Izdatel'stvo Saratovskogo universiteta, 2012, 192 p. (in Russian)

AbrosimovM.B., KamilI.A.K., LobovA.A. Postroenie vsekh neizomorfnykh minimal'nykh vershinnykh rasshirenii grafa metodom kanonicheskikh predstavitelei // Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika. 2019. vol. 19, no. 4. pp. 479–486.

Kamil I.A.K., Lobov A.A., Abrosimov M.B. Construction of minimum vertex extensions of a graph by the Read-Faradzhev method // International Journal of Open Information Technologies. 2020. Т. 8. № 4. С. 54-58.

Abrosimov M.B. Minimal'nye rasshireniya 4-,5-,6- i 7-vershinnyh grafov. Saratov Univ. - Saratov, 2000. – 26с.; Dep. In VINITI 06.09.2000, №2352-В00. (in Russian)

Abrosimov M.B. On the complexity of some problems related to graph extensions. Math. Notes, 2010, vol. 88, no. 5, pp. 619–625.

Volga Regional Center for New Information Technologies. Available at:

Abrosimov M.B. Minimal'nye k-rasshireniya predpolnyh grafov. Izvestiya vysshih uchebnyh zavedenij. Matematika. 2003, № 6, pp. 3-11. (in Russian)

Abrosimov M.B. Harakterizaciya grafov s zadannym chislom dopolnitel'nyh reber minimal'nogo vershinnogo 1-rasshireniya. Prikladnaya diskretnaya matematika, 2012, № 1, pp. 111–120. (in Russian)

Leighton F.T. Introduction to Parallel Algorithms and Architecture: Arrays,•Trees,•Hypercubes. San Mateo, Morgan Kaufmann, 1992, 852 с.

Lobov A.A., Abrosimov M.B. O vershinnom 1-rasshirenii giperkuba. Komp'yuternye nauki i informacionnye tekhnologii. Materialy Mezhdunarodnoj nauchnoj konferencii, 2018, pp. 249-251. (in Russian)


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162