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

Abstract

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.