Geodesic
About minimal $1$-edge extension of hypercube
Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 109-111.

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

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

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

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

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

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

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

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

[7] Meringer M., “Fast generation of regular graphs and construction of cages”, J. Graph Theory, 30 (1999), 137–146 | 3.0.CO;2-G class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl