Construction of all minimal edge extensions of the graph with isomorphism rejection

M. B. Abrosimov ; H. H. K. Sudani ; A. A. Lobov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 20 (2020) no. 1, pp. 105-115

Résumé

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.