About the uniqueness of the minimal 1-edge extension of a hypercube

A graph G is a k-edge extension of a graph G if every graph obtained by removing any k edges from G contains G. A k-edge extention G of a graph G is said to be minimal if it contains n vertices, where n is the number of vertices in G, and G has the minimum number of edges among all k-edge extensions of the graph G with n vertices. The hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. We propose a family of graphs Q n whose representatives for n > 1 are minimal 1-edge extensions of the corresponding hypercubes. The computational experiment showed that for n 6 4 these extensions are unique up to isomorphism. In this paper, we succeeded in obtaining an analytical proof of the uniqueness of minimal 1-edge extensions of hypercubes for n 6 4, as well as establishing one general property of an arbitrary minimal 1-edge extension of a hypercube for n > 2.

Keywords

Authors

References