Geodesic
About uniqueness of the minimal $1$-edge extension of~hypercube $Q_4$
Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 84-93.

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

One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, we can use the graph theory. In this paper, minimal edge extensions of graph are considered as a model for studying the failure of links in a computing system. 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 graph $G$ is said to be minimal if it contains $n$ vertices, where $n$ is the number of vertices of $G$, and $G^*$ has the minimum number of edges among all $k$-edge extensions of 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. In this paper, we provide 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 $Q_n$ for $n > 2$: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to $2$.
Keywords: graph, edge fault tolerance, minimal $1$-edge extension.
Mots-clés : hypercube 
@article{PDM_2022_4_a7,
     author = {A. A. Lobov and M. B. Abrosimov},
     title = {About uniqueness of the minimal $1$-edge extension of~hypercube $Q_4$},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {84--93},
     publisher = {mathdoc},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2022_4_a7/}
}
TY  - JOUR
AU  - A. A. Lobov
AU  - M. B. Abrosimov
TI  - About uniqueness of the minimal $1$-edge extension of~hypercube $Q_4$
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2022
SP  - 84
EP  - 93
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2022_4_a7/
LA  - ru
ID  - PDM_2022_4_a7
ER  - 
%0 Journal Article
%A A. A. Lobov
%A M. B. Abrosimov
%T About uniqueness of the minimal $1$-edge extension of~hypercube $Q_4$
%J Prikladnaâ diskretnaâ matematika
%D 2022
%P 84-93
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2022_4_a7/
%G ru
%F PDM_2022_4_a7
A. A. Lobov; M. B. Abrosimov. About uniqueness of the minimal $1$-edge extension of~hypercube $Q_4$. Prikladnaâ diskretnaâ matematika, no. 4 (2022), pp. 84-93. http://geodesic.mathdoc.fr/item/PDM_2022_4_a7/

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

[2] Abrosimov M. B., Graph Models of Fault Tolerance, SSU Publ., Saratov, 2012, 192 pp. (in Russian)

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

[4] Harary F. and Hayes J. P., “Node fault tolerance in graphs”, Networks, 27 (1996), 19–23 | 3.0.CO;2-H class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR

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

[6] Lobov A. A. and Abrosimov M. B., “On the vertex 1-extension of a hypercube”, Komp'yuternye nauki i informatsionnye tekhnologii, “Nauka” Publ., Saratov, 2018, 249–251 (in Russian)

[7] Zhang Y., Zhao S., and Meng J., “Edge fault tolerance of graphs with respect to $\lambda$2-optimal property”, Theor. Comput. Sci., 783 (2019), 95–104 | DOI | MR

[8] Liu H. and Cheng D., “Structure fault tolerance of balanced hypercubes”, Theor. Comput. Sci., 845 (2020), 198–207 | DOI | MR

[9] Bogomolov A. M. and Saliy V. N., Algebraic Foundations of the Discrete Systems Theory, Nauka Publ., M., 1997, 368 pp. (in Russian) | MR

[10] Harary F., Graph Theory, Addison-Wesley, 1969, 274 pp. | MR

[11] 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

[12] Abrosimov M. B., “On the complexity of some problems related to graph extensions”, Math. Notes, 88:5 (2010), 619–625 | DOI | MR

[13] Abrosimov M. B., Kamil I. A. K., and Lobov A. A., “Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives”, Izv. Saratov Univ. (N. S.), Ser. Matematika. Mekhanika. Informatika, 19:4 (2019), 479–486 (in Russian) | MR

[14] Abrosimov M. B., Sudani Kh. Kh. K., and Lobov A. A., “Construction of all minimal edge extensions of the graph with isomorphism rejection”, Izv. Saratov Univ. (N. S.), Ser. Matematika. Mekhanika. Informatika, 20:1 (2020), 105–115 (in Russian) | MR