Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection

Abstract

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.

Keywords

• fault tolerance
• edge fault tolerance
• graph extension
• isomorphism rejection
• canonical form
• method of generating canonical representatives
• read-faradjev-type orderly algorithm.