Applied Theory of Coding and Graphs
About the uniqueness of the minimal $1$-edge extension of a hypercube
A. A. Lobov,
M. B. Abrosimov Saratov State University
Abstract:
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
$Q_n$ is a regular
$2^n$-vertex graph of order
$n$, which is the Cartesian product of
$n$ complete
$2$-vertex graphs
$K_2$. 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 \leq 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 \leq 4$, as well as establishing one general property of an arbitrary minimal
$1$-edge extension of a hypercube for
$n > 2$.
Keywords:
graph, hypercube, edge fault tolerance, minimal $1$-edge extension.
UDC:
519.17
DOI:
10.17223/2226308X/15/26