RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2022 Issue 15, Pages 110–112 (Mi pdma591)

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



© Steklov Math. Inst. of RAS, 2025