Abstract:
A 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$. For any integer $n>1$, we define a graph $Q^*_n$ by connecting each vertex $v$ in $Q_n$ with one which is most far from $v$. It is shown that $Q^*_n$ is the minimal $1$-edge extension of the hypercube $Q_n$. The computational experiment shows that for each $n\leq4$ this extension is unique up to isomorphism.