Uniqueness of minimal 1-edge extension of hypercubes

Abstract

In 1976 J. P. Hayes proposed a scheme of fault tolerant system construction based on graph theory. In scheme system is modeled by graph. System nodes and links are modeled by graph vertexes and edges or arcs between them. The problem is to build a system which keep functionality after fixed number of nodes fault. Element fault is modeled by corresponding vertex removing. -fault tolerance is achieved by adding spare nodes and links into system so that original system graph embed to every graph obtained by removing  vertexes from graph corresponding to fault tolerant system. In 1993 F. Harary and J. P. Hayes extended problem to the case of  link faults. Link fault is modeled by edge or arc removing. In the paper we name -vertex and -edge fault tolerant system realization vertex and edge -extension. F. Harary and J. P. Hayes found a scheme of hypercube minimal edge 1-extension construction. Edge ‑extension of -vertex graph is called minimal if it has n vertexes and there are no edge -extension of that graph with less number of edges exists. -dimentional hypercube is a graph which vertexes can be labeled by all possible -element binary vectors so that edge connect two vertexes if and only if Hamming distance between their labels is equals 1. The uniqueness of minimal edge 1-extension of 2-, 3- and 4‑dimentional hypercube have been proven. In this paper for  the uniqueness of minimal edge 1‑extension of -dimentional hypercube is shown.