Vertex extensions of $4$-layer graphs and hypercubes

A. A. Lobov ; M. B. Abrosimov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 4, pp. 536-548

Résumé

J. P. Hayes proposed a graph-based model of fault tolerant systems, which in a more abstract form corresponds to vertex and edge extensions of graphs. A graph $G^*$ is called a vertex $k$-extension of a graph $G$ if the graph $G$ is embedded in every graph obtained from $G^*$ by removing any $k$ vertices. If no proper part of the graph $G^*$ is a vertex $k$-extension of the graph $G$, then the extension $G^*$ is said to be irreducible. If a vertex $k$-extension has the minimum possible number of vertices and edges, then it is called minimal. The task of finding minimal extensions for an arbitrary graph is computationally difficult. Only for some classes of graphs, it was possible to find a partial or complete description of their minimal vertex extensions. In this paper, we propose a general scheme for constructing vertex $1$- and $2$-extensions for almost all bipartite graphs, including hypercubes. The hypercube is an interesting graph in terms of its properties and the possibility of using it as a topology of an interconnection network. The minimum vertex extensions for hypercubes are unknown. In practice, trivial $1$-extensions are used, which are obtained by adding one vertex and connecting it to all the others. The irreducible $1$-extension for the $16$-vertex hypercube proposed in this paper contains one less edge than the trivial $1$-extension. The article also determines the number of non-isomorphic extensions for each hypercube that can be constructed using the proposed schemes and proves the irreducibility of hypercube vertex $1$-extensions.