Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика (Mar 2020)
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