Geodesic
Vertex extensions of $4$-layer graphs and hypercubes
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 4, pp. 536-548.

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

J. P. Hayes proposed a graph-based model of fault tolerant systems, which in a more abstract form corresponds to vertex and edge extensions of graphs. A graph $G^*$ is called a vertex $k$-extension of a graph $G$ if the graph $G$ is embedded in every graph obtained from $G^*$ by removing any $k$ vertices. If no proper part of the graph $G^*$ is a vertex $k$-extension of the graph $G$, then the extension $G^*$ is said to be irreducible. If a vertex $k$-extension has the minimum possible number of vertices and edges, then it is called minimal. The task of finding minimal extensions for an arbitrary graph is computationally difficult. Only for some classes of graphs, it was possible to find a partial or complete description of their minimal vertex extensions. In this paper, we propose a general scheme for constructing vertex $1$- and $2$-extensions for almost all bipartite graphs, including hypercubes. The hypercube is an interesting graph in terms of its properties and the possibility of using it as a topology of an interconnection network. The minimum vertex extensions for hypercubes are unknown. In practice, trivial $1$-extensions are used, which are obtained by adding one vertex and connecting it to all the others. The irreducible $1$-extension for the $16$-vertex hypercube proposed in this paper contains one less edge than the trivial $1$-extension. The article also determines the number of non-isomorphic extensions for each hypercube that can be constructed using the proposed schemes and proves the irreducibility of hypercube vertex $1$-extensions. 
@article{ISU_2022_22_4_a9,
     author = {A. A. Lobov and M. B. Abrosimov},
     title = {Vertex extensions of $4$-layer graphs and hypercubes},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {536--548},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2022_22_4_a9/}
}
TY  - JOUR
AU  - A. A. Lobov
AU  - M. B. Abrosimov
TI  - Vertex extensions of $4$-layer graphs and hypercubes
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2022
SP  - 536
EP  - 548
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ISU_2022_22_4_a9/
LA  - ru
ID  - ISU_2022_22_4_a9
ER  - 
%0 Journal Article
%A A. A. Lobov
%A M. B. Abrosimov
%T Vertex extensions of $4$-layer graphs and hypercubes
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2022
%P 536-548
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ISU_2022_22_4_a9/
%G ru
%F ISU_2022_22_4_a9
A. A. Lobov; M. B. Abrosimov. Vertex extensions of $4$-layer graphs and hypercubes. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 4, pp. 536-548. http://geodesic.mathdoc.fr/item/ISU_2022_22_4_a9/

[1] Bogomolov A. M., Salii V. N., Algebraic Foundations of the Theory of Discrete Systems, Fizmatlit, M., 1997, 368 pp. (in Russian) | MR

[2] Abrosimov M. B., Graph Models of Fault Tolerance, Saratov University Publ, Saratov, 2012, 192 pp.

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

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

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

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

[7] Abrosimov M. B., Kamil I. A. K., Lobov A. A., “Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives”, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 19:4 (2019), 479–486 (in Russian) | DOI | MR

[8] Abrosimov M. B., Sudani H. H. K., Lobov A. A., “Construction of all minimal edge extensions of the graph with isomorphism rejection”, Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 20:1 (2020), 105–115 (in Russian) | DOI | MR

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

[10] Biggs N. L., “Distance-transitive graphs”, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974, 155–163 | DOI | MR