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

A. A. Lobov ; M. B. Abrosimov

Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 110-112

Résumé

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$.

Détail

Keywords: graph, edge fault tolerance, minimal $1$-edge extension.
Mots-clés : hypercube