Geodesic
About the uniqueness of the minimal $1$-edge extension of a hypercube
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 110-112.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, edge fault tolerance, minimal $1$-edge extension.
Mots-clés : hypercube 
@article{PDMA_2022_15_a25,
     author = {A. A. Lobov and M. B. Abrosimov},
     title = {About the uniqueness of the minimal $1$-edge extension of a hypercube},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {110--112},
     publisher = {mathdoc},
     number = {15},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a25/}
}
TY  - JOUR
AU  - A. A. Lobov
AU  - M. B. Abrosimov
TI  - About the uniqueness of the minimal $1$-edge extension of a hypercube
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 110
EP  - 112
IS  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a25/
LA  - ru
ID  - PDMA_2022_15_a25
ER  - 
%0 Journal Article
%A A. A. Lobov
%A M. B. Abrosimov
%T About the uniqueness of the minimal $1$-edge extension of a hypercube
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 110-112
%N 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a25/
%G ru
%F PDMA_2022_15_a25
A. A. Lobov; M. B. Abrosimov. About the uniqueness of the minimal $1$-edge extension of a hypercube. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 110-112. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a25/

[1] Padua D. A., Encyclopedia of Parallel Computing, Springer, N.Y., 2011 | Zbl

[2] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp.

[3] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C.25:9 (1976), 875–884 | DOI | MR

[4] Harary F. and Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[5] Lobov A. A., Abrosimov M. B., “O vershinnom 1-rasshirenii giperkuba”, Kompyuternye nauki i informatsionnye tekhnologii, Materialy Mezhdunar. nauch. konf., Izdat. tsentr «Nauka», Saratov, 2018, 249–251

[6] Lobov A. A., Abrosimov M. B., “O minimalnom rebernom 1-rasshirenii giperkuba”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 109–111

[7] Harary F., Hayes J. P., and Wu H.-J., “A survey of the theory of hypercube graphs”, Computers Math. with Appl., 15:4 (1988), 277–289 | DOI | MR | Zbl

[8] Abrosimov M. B., “O slozhnosti nekotorykh zadach, svyazannykh s rasshireniyami grafov”, Matem. zametki, 88:5 (2010), 643–650 | MR | Zbl