Edge fault tolerant extensions of graphs with 8, 9 and 10 vertices

H. H. K. Sudani


Reliability is one of the most important issues in design of technical systems. One way to increase reliability is to build a fault tolerant system implementation. In some systems, link failures between its elements occur. An example is the damage to a communication line in a computer network or the connection point of a wire and a device (socket or connector), which makes it impossible to use a wire and transmit data or electricity through it. In 1993 Frank Harary and John P. Hayes proposed a theoretical graph model for investigating the fault tolerance of discrete systems.

To build a fault tolerant implementation for a system means to find an extension for the corresponding graph. Optimization of the implementation means that the graph must have the minimum possible number of vertices and edges among all the corresponding extensions. The problem of constructing a minimal extension is computationally complex. This article describes a computational experiment on constructing minimal edge extensions of 8-, 9-, and 10-vertex graphs and its results.

Full Text:

PDF (Russian)


Hayes J. P. A graph model for fault-tolerant computing system // IEEE Transactions on Computers. 1976. Vol. C-25. № 9. P. 875–884. DOI: 10.1109/TC.1976.1674712

Harary F., Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. Vol.23. P.135–142. DOI: 10.1002/net.3230230207

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

Bogomolov A.M., Salii V.N. Algebraicheskie osnovy teorii diskretnykh sistem. M.: Nauka 1997. (in Russian)

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., Sudani H. H. K., Lobov A. A. Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2020, vol. 20, iss. 1, pp. 105–115 (in Russian). DOI: https://doi.org/10.18500/1816-9791-2020-20-1-105-115

Brinkmann G. Isomorphism rejection in structure generation programs // Discrete Mathematical Chemistry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. Vol. 51. P. 25-38. DOI: 10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.0.CO;2-U

Kamil I.A.K., Sudani H.H.K., Lobov A.A., Abrosimov M.B. Constructing all nonisomorphic supergraphs with isomorphism rejection // Prikladnaya Diskretnaya Matematika. 2020. № 48. 82–92. DOI: 10.17223/20710410/48/7

Volga Regional Center for New Information Technologies. Available at: http://prcnit.sgu.ru


  • There are currently no refbacks.

Abava  Absolutech Convergent 2020

ISSN: 2307-8162