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

Prikl. Diskr. Mat. Suppl., 2018 Issue 11, Pages 109–111 (Mi pdma392)

This article is cited in 1 paper

Applied Theory of Coding, Automata and Graphs

About minimal $1$-edge extension of hypercube

A. A. Lobov, M. B. Abrosimov

Saratov State University, Saratov

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.

Keywords: graph, hypercube, edge fault tolerance, minimal $1$-edge extension.

UDC: 519.17

DOI: 10.17223/2226308X/11/34



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024