Construction of minimum vertex extensions of a graph by the Read-Faradzhev method

Abstract

In 1976 John Hayes proposed a graph-based model to investigate node fault tolerance of discrete systems. A graph G^* is vertex k-extension of a graph G if after removing any k vertices from G^* result graph contains G. A vertex k-extension of the graph G is called minimal if it has the least number of vertices and edges among all vertex k-extensions of G. Later together with Frank Harary, the model was extended to failures of connections between elements. The problem of verifying a vertex k-extension of a graph is NP-complete. For some types of graphs, it was possible to find an analytical solution to the problem of constructing minimal vertex k-extensions: paths, cycles, stars, etc. In general, a graph can have many nonisomorphic minimal vertex k-extensions. The exhaustive algorithm for constructing all nonisomorphic minimal vertex k-extensions of a given graph can be used only for graphs with a small number of vertices. In some cases, it is possible to find the degree vector of the minimum vertex k-extension, which allows to search much faster. In this paper, we propose an algorithm for constructing all nonisomorphic minimal vertex k-extensions of a given graph with isomorphism rejection by the method of canonical representatives in the Read-Faradzhev form. The implementation of this algorithm in 4 modifications is considered and the results of their work are analyzed.