About uniqueness of the minimal 1-edge extension of hypercube Q₄ | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 58. DOI: 10.17223/20710410/58/8

One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, you can use the apparatus of graph theory. Minimal edge extensions of a graph are considered, which are a model for studying the failure of links in a computing system. A graph G* = (V*,α*) with n vertices is called a minimal k-edge extension of an n-vertex graph G = (V, α) if the graph G is embedded in every graph obtained from G* by deleting any of its k edges and has the minimum possible number of edges. The hypercube Q_n is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K₂. The hypercube is a common topology for building computing systems. Previously, a family of graphs Q*_n was described, whose representatives for n>1 are minimal edge 1-extensions of the corresponding hypercubes. In this paper, we obtain an analytical proof of the uniqueness of minimal edge 1-extensions of hypercubes for n≤4 and establish a general property of an arbitrary minimal edge 1-extension of a hypercube Q_n for n>2: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to 2.